PAGAIN - Prime Again
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
bool isPrime(int n) {
if (n<2) return false; // optional
for (int i=2; i*i<=n; ++i) if (n%i==0) return false;
return true;
}
unsigned long long power(unsigned long long a, unsigned long long d,unsigned long long n)
{
if(d==1) return a%n;
else
{
unsigned long long k = power(a,d/2,n);
if(d%2==0) return k*k%n;
else return ((k*k)%n*a)%n;
}
}
bool rabinMiller(unsigned long long n, int k) {
if (n<=50) return isPrime(n);
unsigned long long d=n-1, s=0;
while (d%2==0) {++s; d/=2;}
for (int i=1; i<=k; ++i) {
unsigned long long a = rand()%(n-2)+2;
unsigned long long x = power(a,d,n);
if (x == 1 || x == n-1) continue;
for (int r=1; r<s; ++r) {
x=(unsigned long long)(x*x) % n;
if (x==1) return false;
if (x==n-1) break;
}
if (x!=n-1) return false;
}
return true;
}
int main()
{
int test;
unsigned long long n;
scanf("%d",&test);
for(int i = 1;i<=test;i++)
{
scanf("%lld",&n);
n--;
while(true)
{
if(rabinMiller(n,20))
{
printf("%lld\n",n);
break;
}
n--;
}
}
// getch();
}