POJ1811-Prime Test【数论】

dzy posted @ 2013年7月14日 14:25 in POJ with tags POJ 数论 , 2238 阅读

关键算法:

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;
}
Avatar_small
Digital Ali 说:
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

Avatar_small
Emma 说:
2023年1月22日 20:33

The Miller-Rabbin and Pollard-Rho algorithms provide an effective way to test for prime numbers. Miller-Rabbin is used to make a decision on whether a number is prime, while Pollard-Rho is diamonds rings for cheap used to find any factor of an integer. Both of these algorithms are incredibly useful in the field of number theory, allowing for efficient and reliable solutions to complex problems. With the Miller-Rabbin's dichotomous approach to finding the smallest factor, you can rest assured that you will find the most accurate result.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter