Fermat素数测试法

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

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-

发表评论

电子邮件地址不会被公开。 必填项已用*标注