hdoj_2138How many prime numbers

How many prime numbers

Time Limit: 3000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7324Accepted Submission(s): 2446

Problem Description

Give you a lot of positive integers, just to find out how many prime numbers there are.

Input

There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.

Output

For each case, print the number of prime numbers you have found out.

Sample Input

3
2 3 4

Sample Output

2



#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

ll exp_mod(ll a,ll b,ll mod)
{
	ll res = 1;
	while(b){
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

bool Miller_Rabbin(ll n)
{
	ll a,s = (n-1) >> 2,i = 1, t = n-1;
	s = min(s,(ll)50);
	do{
		a = rand() % (t) + 1;
		if(exp_mod(a,t,n) != 1) return false;
	}while(i++ < s);
	return true;
}

int main()
{
	int n,ans;
	ll num;
	while(scanf("%d",&n)!=EOF)
	{
		ans = 0;
		for(int i = 0;i < n;i++)
		{
			scanf("%I64d",&num);
			if(Miller_Rabbin(num))
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}