学步园

伪素数：如果n是一个正整数，如果存在和n互素的正整数a满足a^n-1≡1(mod
n)｛a^n-1次方modn等于1｝，我们说n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是素数。（即下面的费马小定理）

费马小定理是数论中的一个重要定理,其内容为:
假如p是质数，且(a,p)=1，那么 a^(p-1) ≡１（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。

这种算法可以快速地测试一个数是否满足素数的必要条件，但不是充分条件。不过也可以用它来测试素数，出错概率很小, 对于任意奇数n>2和正整数s,该算法出错概率至多为2^(-s)，因此，增大s可以减小出错概率，一般取s=50就足够了。

#include<iostream>
#include<cmath>
#include<time.h>
#include<stdio.h>
using namespace std;

__int64 mod_exp(__int64 a,__int64 b,__int64 n)//快速幂取模
{
   __int64 m=1;
   while(b)
   {
      if(b&1) m=(m%n)*(a%n)%n;
      b>>=1;
      a=(a%n)*(a%n)%n;
   }
   return m;
}

bool miller_rabbin(__int64 n)
{
	__int64 i,a;
	for(i=0;i<50;i++)
	{
	  a=rand()%(n-2)+2;
	  if(mod_exp(a,n-1,n)!=1)
		  return false;
	}
	return true;
}

int main()
{
   __int64 n,d=2;
   int t;
   scanf("%d",&t);
   while(t--)
   {
	   scanf("%I64d",&n);
	   if(n==2||miller_rabbin(n)&&n!=1)
		   printf("Prime\n");
	   else
	   {
		   printf("Not prime\n");
	   }
   }
   return 0;
}