How many prime numbers

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

Total Submission(s): 19579 Accepted Submission(s): 6696

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

Sample Output

Author

wangye

Source

Recommend

威士忌 | We have carefully selected several similar problems for you:

Miller_Rabin

测试 15次TLE，5次A了

有谁知道他的时间复杂度吗？

#include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;int n,ans;LL p;LL mul(LL a,LL b){    LL r=0;    while(b)    {        if(b&1) b--,r+=a,r%=p;        a<<=1; a%=p; b>>=1;    }    return r;}LL qm(LL a,LL b){    LL r=1;    while(b)    {        if(b&1) r=mul(r,a);        b>>=1; a=mul(a,a);    }    return r;}bool Miller_Rabin(){    if(p==2) return true;    if(p%2==0) return false;    int T=5;    LL m=p-1,k=0,a,x,y;    while(m%2==0) k++,m>>=1;    while(T--)    {        a=rand()%(p-1)+1;        x=qm(a,m);        for(int i=1;i<=k;i++)        {            y=mul(x,x);            if(x&1 && y==1 && x!=1 && x!=-1) return false;            x=y;        }        if(x!=1) return false;    }    return true;}int main(){    srand(time(0));    while(scanf("%d",&n)!=EOF)    {        ans=0;         while(n--)        {            scanf("%lld",&p);            if(Miller_Rabin()) ans++;        }        printf("%d\n",ans);    }}