由 dawei #include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define M 12
unsigned long long int Pr(unsigned long long int a,unsigned long long int b,unsigned long long int n)
{
unsigned long long ret = 1,pw = a;
while (b!=0)
{
if (b & 1 == 1)
ret = (ret*pw) % n;
pw = (pw*pw) % n;
b >>= 1;
}
return ret;
}
int Preses(unsigned long long int n)
{
if (n <= 3)
{
if (n == 2 || n ==3)
return 1;
else
return 0;
}
else if (n % 2 == 0 || n%3 == 0)
{
return 0;
}
else
{
time_t ts;
unsigned int sum = time(&ts);
srand(sum);
for (int i = 0;i < M;i++)
{
unsigned long long int a = (rand() % (n – 2)) + 2;
unsigned long long int x = a;
unsigned long long int count = 0;
unsigned long long int u = n – 1;
while (u % 2 == 0)
{
u = u / 2;
}
/*while (count < u-1)
{
x *= a;
x %= n;
count += count;
}*/
x = Pr(a,u,n);
while (u < n)
{
unsigned long long int y = (x * x) % n;
if (y == 1 && x != 1 && x != n – 1)
{
return 0;
}
x = y;
u = u * 2;
}
if (x != 1)
{
return 0;
}
}
return 1;
}
}
int main()
{
int sum = 0;
scanf(“%d”,&sum);
unsigned long long int *p = (unsigned long long int *)malloc(sizeof(unsigned long long int) * sum);
for (int i = 0; i < sum; i++)
{
scanf(“%lld”,&p[i]);
}
for (int i = 0; i < sum; i++)
{
int key = Preses(p[i]);
if (key == 1)
{
printf(“YES\n”);
}
else
{
printf(“NO\n”);
}
}
system(“pause”);
return 0;
}
