互质数:公约数为1叫互质数。
这是求最大公约数的方法:
public static int Euclid(int p, int q){
int temp = 0;if(p == 0 || q ==0) return 1;System.out.println("p = " + p +" q = " + q);if(p < q){ //这里是判断了大小temp = q;q = p;p = temp;}
if( (p % q) == 0) return q;
return Euclid(q,(p % q));//每次递归都是从新设定的p和q的值。
}
当公约数为1时即为互质数。