java最大公约数算法

Python016

java最大公约数算法,第1张

//求最大公约数：较大的数除以较小的数，然后将较小的数作为下一次的大数，余数作为小数，直到较小的数为0，返回较大的数

public static int big(int num1,int num2){

int big = 0

int small = 0

if(num1>num2){

big = num1

small = num2

}else{

big = num2

small = num1

}

if(small==0){

System.out.println("除数不能为0")

return 0

}

while(true){

if(small==0){

return big

}else{

int temp = big

big = small

small = temp%small

}

}

}

public class Gcd {

public static void main(String[] args) {

for(int i=0i<10i++) {

int a=(int)(Math.random()*99+1)

int b=(int)(Math.random()*99+1)

System.out.println(a+","+b+"\t=>\t"+getNumber(a,b))

}

}

public static int getNumber(int m,int n){

    if (m % n == 0) {

        return n

    }

    else {

        return getNumber(n,m % n)

    }

}

}

1.从1开始循环。分别求出m、n的约数。找出最大公约数。

2.判断m、n的大小，从较小的开始循环，每次减一，判断是否为公约数。如果是，则为最大公约数，break；

3.2反过来，从小到大循环，找最大的。

公约数判断：

m%i=0&&n/i=0。

举第二个例子：

public

class

Test

{

public

static

int

getN(int

m,int

n){

int

i

=

m>n?n:m

for(i>0i--){

if(m%i==0&&n%i==0){

System.out.println("m、n的最大公约数为"+i)

break

}

}

return

i

}

public

static

void

main(String[]

args)

{

System.out.println(getN(100,

88))

}

}