[poj 1811]質量分解
タイトルリンクは,1つの数を与え,素数であるか否かを判断し,合数であれば最小の質量因子を出力する.
matrix 67大牛の文章、詳しく話して、好評です!
Pallord−rhoアルゴリズムは本質的にランダムな数xでgcd(x,n)がnの約数であるか否かを判断する
期待時間複雑度:O(n 14∗logn)
Miller−rabinアルゴリズムは,Fermaの小さな定理と二次検出により,この数が素数であるか否かを判断し,強い疑似素数を扱うことができる.
このアルゴリズムの正解率は1−(14)k(kは選択した強い擬似証拠の群数)であった.
時間複雑度:O(k∗logn)
必ず手書きで素早く乗るように注意してください.そうしないと爆発します...
matrix 67大牛の文章、詳しく話して、好評です!
Pallord−rhoアルゴリズムは本質的にランダムな数xでgcd(x,n)がnの約数であるか否かを判断する
期待時間複雑度:O(n 14∗logn)
Miller−rabinアルゴリズムは,Fermaの小さな定理と二次検出により,この数が素数であるか否かを判断し,強い疑似素数を扱うことができる.
このアルゴリズムの正解率は1−(14)k(kは選択した強い擬似証拠の群数)であった.
時間複雑度:O(k∗logn)
必ず手書きで素早く乗るように注意してください.そうしないと爆発します...
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
template<class Num>void read(Num &x)
{
char c; int flag = 1;
while((c = getchar()) < '0' || c > '9')
if(c == '-') flag *= -1;
x = c - '0';
while((c = getchar()) >= '0' && c <= '9')
x = (x<<3) + (x<<1) + (c-'0');
x *= flag;
return;
}
template<class Num>void write(Num x)
{
if(x < 0) putchar('-'), x = -x;
static char s[20];int sl = 0;
while(x) s[sl++] = x%10 + '0',x /= 10;
if(!sl) {putchar('0');return;}
while(sl) putchar(s[--sl]);
}
const int Case = 3, prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 61, 24251}, tot = 16;
const long long LINF = 1LL << 60;
long long N, ans;
long long Mult_Mod(long long a,long long k,long long p)
{
long long r = 0;
a %= p;
while(k)
{
if(k&1) r += a, r %= p;
a <<= 1, a %= p, k >>= 1;
}
return r;
}
long long Power_Mod(long long a,long long k,long long p)
{
long long r = 1;
a %= p;
while(k)
{
if(k&1) r = Mult_Mod(r, a, p);
a = Mult_Mod(a, a, p), k >>= 1;
}
return r;
}
long long gcd(long long a,long long b)
{
return b ? gcd(b, a % b) : a;
}
long long Pollard_Rho(long long n)
{
long long f = rand()%n, g = f, t;
while(true)
{
for(int i = 0; i <= 1; i++)
{
g = (Mult_Mod(g, g, n) + 1) % n;
t = gcd(llabs(g - f), n);
if(t != 1 && t != n) return t;
if(f == g) return n;
}
f = (Mult_Mod(f, f, n) + 1) % n;
}
}
bool Miller_Rabin(long long n)
{
if(n == 2) return true;
if(!(n&1)) return false;
long long y = n - 1;
int t = 0;
while(!(y&1)) y >>= 1, t++;
for (int i = 0; i < tot; i++)
{
if(n == prime[i]) return true;
long long f = Power_Mod(prime[i], y, n), g = f;
for(int j = 1; j <= t; j++)
{
f = Mult_Mod(f, f, n);
if(f == 1 && g != 1 && g != n - 1) return false;
g = f;
}
if(f != 1) return false;
}
return true;
}
void solve(long long n)
{
if(Miller_Rabin(n))
{
ans = std::min(n, ans);
return;
}
for(int i = 1; i <= Case; i++)
{
long long p = Pollard_Rho(n);
if(p != n)
{
solve(p), solve(n/p);
return;
}
}
}
int main()
{
int T;
#ifndef ONLINE_JUDGE
freopen("1811.in","r",stdin);
freopen("1811.out","w",stdout);
#endif
srand(23333);
read(T);
while(T--)
{
read(N);
ans = N;
solve(N);
if(ans < N)
write(ans), puts("");
else
puts("Prime");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return 0;
}