質數的判斷 C code and Python

我大概寫了一下質數的判斷,使用的方法 AKS primality test

###############
C code ###############

bool isPrimeNum(int num)

{
bool IsPermeflag=true;//False isn't prime,True is prime
int sqrtNum =int(floor(sqrt(num)));
for( int i=2;i<=sqrtNum;i++)
{
if((num%i)==0)
{
IsPermeflag=false;break;
}
}
return IsPermeflag;
}
###############Python ###############
import math
testPermeNumber=13
sqrtNum=int(math.floor(math.sqrt(testPermeNumber)))
IsPermeflag=1
i=2
while i<=sqrtNum: if ( testPermeNumber % i ) == 0: IsPermeflag=0 break i=i+1 print testPermeNumber % i if IsPermeflag: print testPermeNumber,"is perme" else: print testPermeNumber,"isn't perme"

留言

Explorer寫道…
這根本不是AKS,這只是試除法,是個很慢的演算法。
http://zh.wikipedia.org/wiki/%E8%AF%95%E9%99%A4%E6%B3%95

熱門文章