记录编号	106809	评测结果	AAAAAAAAAA
题目名称	1668.[SPOJ 1481] 寻找素数项	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.871 s
提交时间	2014-06-19 20:40:44	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int N=100000;
ll quickpow(ll a,ll n,ll mod){
	ll ans=1;
	while(n){
		if(n&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		n>>=1;
	}
	return ans;
}
bool Rabin_Miller_test(ll n,ll a){//以a为基,n是否成立
	ll temp=n-1;
	while(!(temp&1)) temp>>=1;
	ll m=quickpow(a,temp,n);
	if(m==1) return true;
	while(temp<n){
		if(m==n-1) return true;
		temp<<=1;
		m=(m*m)%n;
	}
	return false;
}
bool Rabin_Miller_test(ll n){//这可以准确判断int范围以内的所有素数
	if(n<=7){
		if(n==2||n==3||n==5||n==7) return true;
		return false;
	}
	if(!(n&1)){
		if(n==2) return true;
		return false;
	}
	if(!Rabin_Miller_test(n,2)) return false;
	if(!Rabin_Miller_test(n,3)) return false;
	if(!Rabin_Miller_test(n,5)) return false;
	if(!Rabin_Miller_test(n,7)) return false;
	return true;
}
bool test(ll n){
	if(n<2) return false;
	for(ll i=2;i<n&&i*i<=n;i++) if(n%i==0) return false;
	return true;
}
void work(void){
	ll a;
	scanf("%lld",&a);
	for(int i=1;i<=N;i++){
		if(Rabin_Miller_test(a)) printf("1");
		else printf("0");
		a=(a+(ll)1234567890)&(ll)0x7fffffff;
	}
}
int main(){
	freopen("primechecker.in","r",stdin);
	freopen("primechecker.out","w",stdout);
	work();
	return 0;
}