学步园

     写了一个判断素数的程序，用的是Miller-Rabin  算法，留下做个模板。。。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <stdlib.h>
using namespace std;
long long mod2(long long a,long long b,long long n)
//计算a*b%n的，防止a*b的时候超过 long long的范围
{
     long long sum=0;
    int i;
    for(i=61;i>=0;i--)
    {
        sum<<=1;
        if(b&( long long)1<<i)
            sum+=a;
        sum%=n;
    }
    return sum;
}
 long long mod( long long a, long long b, long long n)
//模取幕，计算a^b%n；
{
     long long m=1;
    int i=60;
    while(!b&( long long)1<<i)
        i--;
    while(i>=0)
    {
        m=mod2(m,m,n);
        if(b&( long long)1<<i)
            m=mod2(m,a,n);
        i--;
    }
    return m;
}
bool witness( long long a, long long n)
{
    int i=0;
     long long t2,t=n-1;
    while(t%2==0)
    {
        t>>=1;
        i++;
    }
    t=mod(a,t,n);
    for(;i>0;i--)
    {
        t2=mod2(t,t,n);
        if(t2==1&&t!=1&&t!=n-1)
            return true;
        t=t2;
    }
    if(t!=1)
        return true;
    return false;
}
bool miller_rabin( long long n)
{
    int i;
     long long t;
    for(i=0;i<10;i++)//其中10是测试的次数，越大出错率越小，一般应用取10就够
    {
        t=(double)rand()/RAND_MAX*(n-2)+1;
        if(witness(t,n))
        return false;
    }
    return true;
    //n是要测试的正数，如果是质数返回true，合数返回false
}
int main(){
  int numcase;
  scanf("%d",&numcase);
  long long p;//p>1
  while(numcase--){
	scanf("%lld",&p);
	if(miller_rabin(p))puts("Yes");
	else  puts("No");
  }
  return 0;
}