BZOJ 3667:Rabin-Millerアルゴリズム
3284 ワード
適用
しかし、なぜ私の素数テストが間違っている確率が高いのか分かりません.
しかし、なぜ私の素数テストが間違っている確率が高いのか分かりません.
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
#define ll long long
ll n,m;
ll lowbit(ll x){return x&-x;}
const
int maxn=5000000;
bool check[50000001];
int prime[50000001];
int tot;
ll factor[101];
int t;
/*
inline ll mult(ll a,ll x,ll mod)
{
a%=mod,x%=mod;
ll res=0,base=a,i;
for(i=1;i<=x;i<<=1,base<<=1,base%=mod)
if(i&x)res+=base,res%=mod;
return res;
}*/
#define LL ll
inline LL mult(LL a,LL b,LL p)
{
a%=p; b%=p;
LL t=(a*b-(LL)((double)a/p*b+0.5)*p);
return t<0?t+p:t;
}
inline ll pow(ll a,ll x,ll mod)//a^x
{
ll res=1,base=a,i;
for(i=1;i<=x;i<<=1,base=mult(base,base,mod))
if(i&x)res=mult(res,base,mod);
return res;
}
inline ll gcd(ll a,ll b)
{
ll tp;
while(b)
{tp=a%b;a=b;b=tp;}
return a;
}
inline bool Check(ll p)
{
if(p<=maxn)
return !check[p];
if(!(p&1))return false;
ll a=rand()%p;
if(pow(a,p-1,p)!=1)return false;
ll j=lowbit(p-1),m=(p-1)/j,b=rand()%(p-4)+2,v=pow(b,m,p);
if(v==1)return true;
j>>=1;
while(j)
{
if(v==p-1||v==1)return true;
v=mult(v,v,p);
j>>=1;
}
return false;
}
char c;
inline void read(ll &a)
{a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}
inline ll f(ll a,ll n)
{return mult(a,a,n);}
inline ll Rho(ll n)
{
if(n==1)return 1;
ll k=2,x=rand()%n,y=x,p=1,c=rand()%(n-1)+1;
for(ll i=1;p==1;i++)
{
x=(mult(x,x,n)+c)%n;
p=abs(x-y);
p=gcd(n,p);
if(i==k) y=x,k<<=1;
}
return p;
}
void fact(ll n)
{
if(n==1)return;
if(Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n))
factor[++tot]=n;
else
{
ll p=Rho(n);fact(n/p);fact(p);
}
}
int main()
{
int i,j;
srand(10086);
check[1]=true;
check[0]=true;
for(i=2;i<maxn;i++)
{
if(!check[i]) prime[++tot]=i;
for(j=1;j<=tot;j++)
if(prime[j]*1ll*i>maxn)break;
else if(i%prime[j]==0){check[prime[j]*i]=true;break;}
else
check[prime[j]*i]=true;
}
ll T,tp;
ll n;
read(T);
while(T--)
{
read(n);tp=n;
if(Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n)&&Check(n))
puts("Prime");
else
{
tot=0;
fact(tp);
ll ans=-1;
if(tot==1){ puts("Prime");continue;}
for(i=1;i<=tot;i++)
if(ans<factor[i])ans=factor[i];
printf("%lld
",ans);
if(ans==1781707)
ans++;
}
}
return 0;
}