|
试题描述
|
|
现在有一大堆数，请你对这些数进行检验。
|
|
输入
|
|
第一行：CAS,代表数据组数（不大于500000），以下CAS行，每行一个数字，保证在64位长整形范围内，并且没有负数。你需要对于每个数字检验是否是质数。
|
|
输出
|
|
共一行，输出质数的数量，保证是在64位长整形范围内的正数。
|
|
输入示例
|
|
4 2 3 5 4
|
|
输出示例
|
|
3
|
|
其他说明
|
|
数据范围： 保证cas<=100000，保证所有数字均在64位长整形范围内。 请尽量优化你的程序，包括OI优化。 欢迎暴力法不服来辩呦→ →
|
首先有这样一个定理：
若p是一个质数，x是一个整数，且x^2 mod p = 1，那么x ≡ ±1 (mod p)。
证明：x^2 mod p = 1 -> p | x^2 - 1 -> p | (x - 1)(x + 1)，又因为p是质数故x-1与x+1中有一个是p的倍数。
但这个定理的逆定理是个假命题，不过它很少有反例。我们就可以利用逆定理来判定素数了。
设待测数为n，任取一个比n小的正整数a，设 n - 1 = r * 2^s，若n是质数则以下条件至少有一个成立：
1.a^s mod n = 1
2.存在一个整数i满足：0<=i<s且a^(d*(2^i)) mod n = -1
重复以上步骤3至4次即可稳定出解。
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
ll pow(ll n,ll m,ll p) {
ll ans=,t=n;
while(m) {
if(m&) (ans*=t)%=p;
(t*=t)%=p;m>>=;
}
return ans;
}
int check(ll a,ll n,ll r,ll s) {
ll ans=pow(a,r,n);if(ans==) return ;
rep(,s) {
if(ans==n-) return ;
(ans*=ans)%=n;
}
return ;
}
int isprime(ll n) {
if(n==) return ;
if(n<=||!(n&)) return ;
int r=n-,s=;
while(!(r&)) r>>=,s++;
rep(,) if(check(rand()%(n-)+,n,r,s)) return ;
return ;
}
int main() {
int T=read(),ans=;
while(T--) ans+=isprime(read());
printf("%d\n",ans);
return ;
}