poj 1811(素数判定+素因数分解)
題意:64ビットの整数を与え、質量数かどうかを尋ね、そうでなければ最小因子を出力します.
分析:経典の問題の数学の問題、与える数は大きすぎて、普通の方法はきっとタイムアウトして、ネット上でこのアルゴリズムを探しました
miller_rabbin素数判定.そうでなければpollard_rhoは質因子を分解し,最小を見つければよい.
Miller−rabinアルゴリズムは、正の整数が素数であるか否かを迅速に判断するためのアルゴリズムである.それは,pが質量数であり,a,pが互いに質量である場合,a^(p−1)mod pは一定1に等しいというFermaの小さな定理を利用した.すなわち、p未満のすべての正の整数aについて、a^(p−1)mod pを複合して1に等しくしなければならない.では,逆否命題によれば,1つのpに対して,a(aしかし,各試行の過程で最適化操作を行い,pが素数ではないことを少量のaで検出する確率を高めた.この最適化を二次プローブと呼ぶ.これは、pが素数である場合、x(0pollard-rho
これは整数を素因数分解するためのアルゴリズムであり,Miller‐rabinとの共同使用が必要である.nの質因子を求める基本過程は,まずnが素数であるか否かを判断し,そうでなければ1つの擬似乱数生成過程に従って乱数シーケンスを生成し,生成された乱数毎にnと互いに質があるか否かを判断し,質が合えば次の乱数を試みる.互いに質を持たない場合は,その公因子をpとし,pとn/pの因子を再帰的に解く.nが素数である場合、nはその素数として直接返される.
分析:経典の問題の数学の問題、与える数は大きすぎて、普通の方法はきっとタイムアウトして、ネット上でこのアルゴリズムを探しました
miller_rabbin素数判定.そうでなければpollard_rhoは質因子を分解し,最小を見つければよい.
Miller−rabinアルゴリズムは、正の整数が素数であるか否かを迅速に判断するためのアルゴリズムである.それは,pが質量数であり,a,pが互いに質量である場合,a^(p−1)mod pは一定1に等しいというFermaの小さな定理を利用した.すなわち、p未満のすべての正の整数aについて、a^(p−1)mod pを複合して1に等しくしなければならない.では,逆否命題によれば,1つのpに対して,a(a
これは整数を素因数分解するためのアルゴリズムであり,Miller‐rabinとの共同使用が必要である.nの質因子を求める基本過程は,まずnが素数であるか否かを判断し,そうでなければ1つの擬似乱数生成過程に従って乱数シーケンスを生成し,生成された乱数毎にnと互いに質があるか否かを判断し,質が合えば次の乱数を試みる.互いに質を持たない場合は,その公因子をpとし,pとn/pの因子を再帰的に解く.nが素数である場合、nはその素数として直接返される.
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
typedef __int64 LL;
const int S=20;// ，S ，
//***************Miller_Rabin ***************
LL mult_mod(LL a,LL x,LL n)// (a*x) mod n,a,x,n<2^63
{
a%=n;x%=n;
LL ret=0;
while(x)
{
if(x&1){ret+=a;if(ret>=n)ret-=n;}
a<<=1;
if(a>=n)a-=n;
x>>=1;
}
return ret;
}
LL pow_mod(LL a,LL x,LL n)// a^x mod n
{
if(x==1)return a%n;
int bit[70],k=0;
while(x)
{
bit[k++]=(x&1?1:0);
x>>=1;
}
LL ret=1;
for(--k;k>=0;k--)
{
ret=mult_mod(ret,ret,n);
if(bit[k])ret=mult_mod(ret,a,n);
}
return ret;
}
bool judge(LL a,LL n,LL x,LL t)// a ，n-1=x*2^t， n
{
LL ret=pow_mod(a,x,n),flag=ret;
for(LL i=1;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret==1&&flag!=1&&flag!=n-1)return true;
flag=ret;
}
if(ret!=1)return true;
return false;
}
bool Miller_Rabin(LL n)
{
if(n==2||n==5||n==7||n==11)return true;
if(n%2==0||n%5==0||n%7==0||n%11==0)return false;
LL x=n-1,t=0;
while((x&1)==0)x>>=1,t++;
bool flag=true;
if(t>=1&&(x&1)==1)
{
for(int i=1;i<=S;i++)
{
LL a=rand()%(n-1)+1;
if(judge(a,n,x,t)){flag=true;break;}
flag=false;
}
}
if(flag)return false;
else return true;
}
//*******pollard_rho *****************
LL factor[100];//
int tot;//
LL gcd(LL a,LL b)
{
if (a==0) return 1;
if (a<0) return gcd(-a,b);
while (b)
{
LL t=a%b; a=b; b=t;
}
return a;
}
LL Pollard_rho(LL x,LL c)
{
LL i=1,x0=rand()%x,y=x0,k=2;
while (1)
{
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
LL d=gcd(y-x0,x);
if (d!=1 && d!=x)
return d;
if (y==x0) return x;
if (i==k)
{
y=x0;
k+=k;
}
}
}
void find_factor(LL n) // N
{
if (Miller_Rabin(n))
{
factor[tot++] = n;return;
}
LL p=n;
while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1);
find_factor(p);
find_factor(n/p);
}
int main()
{
int t;
LL n;
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
if(Miller_Rabin(n))
printf("Prime
");
else
{
tot=0;
find_factor(n);
LL minfac=factor[0];
for(int i=1;i<tot;i++)
if(minfac>factor[i])
minfac=factor[i];
printf("%I64d
",minfac);
}
}
return 0;
}