Fermat素数测试法

Posted on 2008/10/10 by 枯藤昏鸦

这个算法是存在“很大”误差的，不过仍是需要掌握滴^_^

Java

public static boolean fermat_prime(int n){ int a=2,power=n-1,other=1; while(power>1){ if(power%2==1){ other*=a; other%=n; } power/=2; a=a*a%n; } if(a*other%n==1){ return true; }else{ return false; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public static boolean fermat_prime(int n){ int a=2,power=n-1,other=1; while(power>1){ if(power%2==1){ other*=a; other%=n; } power/=2; a=a*a%n; } if(a*other%n==1){ return true; }else{ return false; } }

-EOF-