小数字判质数：
[CODE]bool isPrime(int num)
{
int i,limit;
if(num==2) return true;
if((num&1)==0)
return false;
else
{
limit=(int)sqrt((double)(num));
for(i=3;i<=limit;i+=2)
if(num%i==0)
return false;
return true;
}
}[/CODE]
大数判质（拉宾米勒测试）
[CODE]static long long g_aPrimeList[] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499
};
long long Montgomery( long long n, long long p, long long m )
{
long long k = 1;
n %= m;
while ( true )
{
if ( 0 != ( p & 1 ) )
{
if ( p == 1 ) return ( n * k ) % m;
k = ( k * n ) % m;
}
n = ( n * n ) % m;
p >>= 1;
}
}
bool RabbinMillerTest( long long n )
{
const long long nPrimeListSize = sizeof(g_aPrimeList) / sizeof(long long);
for ( int i = 0; i < nPrimeListSize; ++i )
{
if ( n / 2 + 1 <= g_aPrimeList[i] )
{
return true;
}
if ( 0 == n % g_aPrimeList[i] )
{
return false;
}
}
long long r = 0, m = n - 1;
while ( 0 == ( m & 1 ) )
{
m >>= 1;
r++;
}
const int nTestCnt =5;
for ( int i = 0; i < nTestCnt; ++i )
{
long long a = g_aPrimeList[ rand() % nPrimeListSize ];
if ( 1 != Montgomery( a, m, n ) )
{
long long j = 0;
long long e = 1;
for ( ; j < r; ++j )
{
if ( n - 1 == Montgomery( a, m * e, n ) )
{
break;
}
e <<= 1;
}
if ( j == r )
{
return false;
}
}
}
return true;
}[/CODE]
[此贴子已经被作者于2006-12-13 21:34:59编辑过]
