HDU - 2138 How many prime numbers

题目链接：HDU - 2138 How many prime numbers

Time Limit	Memory Limit
3000/1000 MS (Java/Others)	32768/32768 K (Java/Others)

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

题意

就是求有多少个素数，暴力可过。

开始感觉判断整数范围的数不能暴力，研究了好长时间关于素数的算法…可能还是数据太水了吧…

AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool isprim(int n)
{
    if(n<)
        return false;
    for(int i=;i<=sqrt(n);++i)
        if(n%i==)
            return false;
    return true;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans=,a;
        for(int i=;i<n;i++)
        {
            scanf("%d",&a);
            if(isprime(a))
                ans++;
        }
        printf("%d\n",ans);
    }
    return ;
}
           

Miller Rabbin判断大素数法

#include<iostream>
#include<cstdio>
using namespace std ;
long long Montgomery(long long a,int p,int m)
{//计算a^p%m
    long long tmp=;
    a%=m;
    while(p)
    {
        if(p&)
            tmp=(tmp*a)%m;
        a=(a*a)%m;
        p>>=;
    }
    return tmp;
}
bool Miller_Rabbin(int a,int n)
{
    int r=,d=n-;
    while(!(d&))//找到奇数
    {
        d>>=;
        r++;
    }
    long long k=Montgomery(a,d,n);//Montgomery快速幂模
    if(k==)
        return true;//同余1
    for(int i=;i<r;i++,k=k*k%n)
        if(k==n-)
            return true;//同余-1
    return false;
}
bool isprime(long long  n)
{
    int prime[]={,,};
    if(n==||n==||n==||n==)
        return true;
    if(!(n&)||n%==||n==)
        return false;
    for(int i=;i<;i++)
        if(!Miller_Rabbin(prime[i],n))
            return false;
    return true;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans=,a;
        for(int i=;i<n;i++)
        {
            scanf("%d",&a);
            if(isprime(a))
                ans++;
        }
        printf("%d\n",ans);
    }
    return ;
}