題目連結: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 ;
}