HOJ1356素数判断，求大神看看我的code为什么超时？
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<cmath>
using namespace std;
long long judge(long long a, long long b, long long n) //求(a^b) mod n
{
long long d=1,t=a;
while (b>0)
{
if (t==1) return d ;
if (b%2==1) d=d*t%n;
b/=2;
t=t*t%n;
}
return d;
}
int prime(long long n)
{
long long a;
a=rand()%(n-1)+1;
if(judge(a,n-1,n)%n!=1) return 0;
else return 1;
}
int main()
{
long long n;
int t,flag;
while(cin >> n)
{
flag=1;//1为素数
if(n<=1) flag=0;
else if(n==2||n==3) flag=1;
else
{
t=3;
while(t--&&flag)
{
if(!prime(n))
{
flag=0;
}
}
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
[解决办法]
对不起搞错了，2^31这么大的数，只能用概率判素模型
http://www.baidu.com/s?wd=hoj+1356&opt-webpage=on&ie=gbk
