修女再出水

Question

麻烦大家编写求任意从键盘输入的两个数的公约数(要求用以下算法!)
1，将m分解质因数；
2，将n分解质因数；
3，提取m和n中的公共质因数；
4，将m和n中的公共质因数相乘，乘积作为结果输出 例如，要计算gcd(66,12),首先分解质因数66=2*3*11，12=2*2*3， 然后提取二者的公共质因数2*3，则gcd(66,12)=2*3=6 求质因数的步奏没有明确定义（该步奏应该得到一个质因数的数组）

Answer 1

史上最没效率求最大公约数方法之一...import java.util.*;
public class Test32 {
public static void main(String[] args) {
int i1 = 15210;
int i2 = 169*114;
ArrayList<Integer> al1 = new ArrayList<Integer>();
ArrayList<Integer> al2 = new ArrayList<Integer>();
factorizate(i1, al1);
System.out.println(al1);
factorizate(i2, al2);
System.out.println(al2);
ArrayList<Integer> resultList = new ArrayList<Integer>();
for(int i=0; i<al1.size(); i++) {
int m = al1.get(i);
for(int j=0; j<al2.size(); j++) {
if(m == al2.get(j)) {
resultList.add(m);
al2.remove(j);
break;
}
}
}
System.out.println(resultList);
int result = 1;
for (int j = 0; j < resultList.size(); j++) {
result *= resultList.get(j);
} System.out.println(result);
}

public static void factorizate(int number, ArrayList<Integer> al) {
if(number%2 == 0) {
al.add(2);
factorizate(number/2, al);
} else {
int j = (int)Math.sqrt(number);
for(int i=3; i<=j; i+=2) {
if(number%i == 0) {
al.add(i);
factorizate(number/i, al);
return;
}
}
al.add(number);
}
}
}

Answer 2

附赠个...public static int gcd(int a, int b) {
int r;
while(b!=0) {
r = a % b;
a = b;
b = r;
}
return a;
}

Answer 3

再附赠个...符号说明：
(a,b)表示a和b的最大公因数
b|a表示b能够整除a设 a=bq+r （a,b,q,r为正整数，a>b，0<r<b）
求证： (a,b)=(b,r).证明：
1。
设： (a,b)=d ，m,n为两个正整数
则 a=dm, b=dn
r = a-bq = dm - dnq = d( m-nq )
所以有 d|r, 又 d|b
所以 d|(r,b)，则 d<=(r,b)
设(r,b)=D，则有 D>=d
2。
D|b,D|r, 又a=bq+r
所以D|a
又D|b
因此D|(a,b)
所以有 D<=(a,b)=d综合1.2.
得到D=d
得证.

Answer 4

TO zephyr_cc() 
老兄运行不出正确结果啊,你调试了吗?
只需要那个指定的算法啊,再看下吧,谢谢了!