HDU-2138-How many prime numbers(ミラーラビン素数試験)

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 <iomanip>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 100010
using namespace std;
int tab[]={2, 3, 5, 7};
long long qpow(int a, int b, int r)  //(a^b)%r  
{
    long long ret = 1, tmp = a;
    while(b)
    {
        if (b&1)
            ret = ret*tmp%r;
        tmp = tmp*tmp%r;
        b >>= 1;
    }
    return ret; 
}
bool  Miller_Rabbin(int n, int a)//  
{
    int r = 0, s = n-1, j;
    long long k;
    if(n%a == 0)    return false;
    while((s&1) == 0)
    {
        s >>= 1;
        r++;
    }
    k = qpow(a, s, n);
    if(k == 1)  return true;
    for (j = 0; j < r; j++, k=k*k%n)
        if (k == n-1)
            return true;
    return false;
}
bool Isprime(int n)//  
{
    for (int i = 0; i < 4; i++)
    {
        if (n == tab[i])
            return true;
        if (!Miller_Rabbin(n, tab[i]))
            return false;
    }
    return true;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    int n, ans, i, t;
    while(cin >> n)
    {
        ans = 0;
        for (i = 0; i < n; i++)
        {
            cin >> t;
            if(Isprime(t))  ans++;
        }
        cout << ans << endl;
    } 
    return 0;
}