Fermat素数测试法

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;
	}
 
}

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; } }