三种算法求最大公约数-Java代码实现.zip

import java.util.*; /** * 求两个自然数m和n的最大公约数。 * * 分解质因数算法： * 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。 **/ public class GreatestCommonDivisor3 { public static void main(String[] args) { Scanner in=new Scanner(System.in); System.out.println("Please input two integers,m and n: "); int m=in.nextInt(); int n=in.nextInt(); double startTime=System.currentTimeMillis(); /** *将m分解质因数，因子存放在Integer类型的数组maa（由泛型数组列表ma转换而来）中 */ ArrayList<Integer> ma=new ArrayList<Integer>(); for(int i=2;i<=m;i++){ while(m!=i){ if(m%i==0){ ma.add(i);; m=m/i; }else break; } } ma.add(m); Integer[] maa=new Integer[ma.size()]; ma.toArray(maa); /** *将n分解质因数，因子存放在Integer类型的数组naa（由泛型数组列表na转换而来）中 */ ArrayList<Integer> na=new ArrayList<Integer>(); for(int i=2;i<=n;i++){ while(n!=i) { if(n%i==0){ na.add(i);; n=n/i; }else break; } } na.add(n); Integer[] naa=new Integer[na.size()]; na.toArray(naa); /** *比较两个数m和n的质因数，提取公共的质因子，存放到Integer类型数组ga（由泛型数组列表g转换而来）中 */ ArrayList<Integer> g=new ArrayList<Integer>(); for(int i=0;i<ma.size();i++){ int j=0; do{ if(maa[i]==naa[j]){ g.add(maa[i]); ma.remove(i); ma.toArray(maa); } j++; }while(j<na.size()); } Integer[] ga=new Integer[g.size()]; g.toArray(ga); double endTime=System.currentTimeMillis(); /** *用存放在ga中的公共质因子相乘得到m和n的最大公约数gcd，并打印显示出来 */ int gcd=1; for(int i=0;i<ga.length;i++) gcd*=ga[i]; System.out.println("The greatest common divisor is,gcd(m,n)= "+gcd); System.out.println("Basic statements take "+(endTime-startTime)+" milliseconds!"); } }