关键算法:
Miller-Rabbin判断素数。http://www.dxmtb.com/blog/miller-rabbin/
Pollard-Rho找出整数的任意一个因子。http://www.dxmtb.com/blog/pollard-rho/
先跟着他讲的写了一遍。太神了。
找因子的时候因为找出来的是任意一个。所以还要继续二分直到找到最小的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int S=30,C=240; typedef long long ll; ll An; ll mul(ll a,ll b,ll c){ ll r; for(r=0;b;a=(a<<1)%c,b>>=1) if(b&1) r=(r+a)%c; return r; }ll pow(ll a,ll b,ll c){ ll r; for(r=1;b;a=mul(a,a,c),b>>=1) if(b&1) r=mul(r,a,c); return r; }int miller_rabbin(ll n){ if(n==2) return 1; if(n<2||!(n&1)) return 0; int t=0; ll a,x,y,u=n-1; while(!(u&1)) t++, u>>=1; for(int i=0;i<S;i++){ a=rand()%(n-1)+1; x=pow(a,u,n); for(int j=0;j<t;j++){ y=mul(x,x,n); if(y==1&&x!=1&&x!=n-1) return 0; x=y; }if(x!=1) return 0; }return 1; }ll gcd(ll a,ll b){ return (!b)?a:gcd(b,a%b); }ll pollard_rho(ll n,ll c){ ll x,y,d,i=1,k=2; x=rand()%(n-1)+1;y=x; while(++i){ x=(mul(x,x,n)+c)%n; d=gcd(y-x,n); if(1<d&&d<n) return d; if(x==y) return n; if(i==k) y=x,k<<=1; } }void find(ll n,ll c){ ll m; if(n==1) return; if(miller_rabbin(n)){ An=min(An,n); return;} m=n; while(m==n) m=pollard_rho(n,c--); find(m,c); find(n/m,c); }int main(){ int tc; scanf("%d",&tc); ll n; while(tc--){ scanf("%lld",&n); if(miller_rabbin(n)) printf("Prime\n"); else{ An=1ll<<60ll; find(n,1LL*C); printf("%lld\n",An);} }return 0; }
2021年9月07日 16:23
A great content material as well as great layout. Your website deserves all of the positive feedback it’s been getting. I will be back soon for further quality contents. 123 movies