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)
}
}
}
三种算法：//欧几里得算法（辗转相除）：
public static int gcd(int m,int n) {
if(m<n) {
int k=m
m=n
n=k
}
//if(m%n!=0) {
//m=m%n
//return gcd(m,n)
//}
//return n
return m%n == 0?n:gcd(n,m%n)
}
//连续整数检测算法：
public static int gcd1(int m,int n) {
int t
if(m<n) {
t=m
}else {
t=n
}
while(m%t!=0||n%t!=0){
t--
}
return t
}
//公因数法：(更相减损）
public static int gcd2(int m,int n) {
int i=0,t,x
while(m%2==0&n%2==0) {
m/=2
n/=2
i++
}
if(m<n){
t=m
m=n
n=t
}
while(n!=(m-n)) {
x=m-n
m=(n>x)?n:x
n=(n<x)?n:x
}
if(i==0)
return n
else
return (int)Math.pow(2, i)*n
}
public static void main(String[] args) {
System.out.println("请输入两个正整数:")
Scanner scan = new Scanner(System.in)
Scanner scan2=new Scanner(System.in)
int m=scan.nextInt()
int n=scan2.nextInt()
System.out.println("欧几里得算法求最大公约数是:"+gcd(m,n))
System.out.println("连续整数检测算法求最大公约数是:"+gcd1(m,n))
System.out.println("公因数法求最大公约数是:"+gcd2(m,n))
}
}
求最大公约数：提示用户输入两个正整数，并求出它们的最大公约数。
方法一：（辗转相除法）
设用户输入的两个整数为n1和n2且n1>n2，余数=n1%n2。当余数不为0时，把除数赋给n1做被除数，把余数赋给n2做除数再求得新余数，若还不为0再重复知道余数为0，此时n2就为最大公约数。
例：gcd(20,8)
20=2*8+4
8=2*4 因此gcd(20,8)=4
代码实现：
import javax.swing.JOptionPanepublic class GreatestCommonDivisor{ public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:") int num1 = Integer.parseInt(num1String)
String num2String = JOptionPane.showInputDialog("Please enter the second integer:") int num2 = Integer.parseInt(num2String) if(num1<num2){ int temp=num1
num1=num2
num2=temp
} int remainder = num1%num2 int n1=num1,n2=num2 while(remainder!=0){
num1=num2
num2=remainder
remainder=num1%num2
}
JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",n1,n2,num2))
}
}12345678910111213141516171819202122232425262728
方法二：假设输入的两个整数为n1和n2，检查k(k=2,3,4…)是否为n1和n2的最大公约数，直到k大于两个数中较小的一个。
代码实现：
import javax.swing.JOptionPanepublic class GreatestCommonDivisor{ public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:") int num1 = Integer.parseInt(num1String)
String num2String = JOptionPane.showInputDialog("Please enter the second integer:") int num2 = Integer.parseInt(num2String) int gcd=1,k=1 while(k<=num1 &&k<=num2)
{ if(num1%k==0 &&num2%k==0)
gcd=k
k++
}
JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",num1,num2,gcd))
}
}12345678910111213141516171819202122
方法三：假设输入的两个整数为n1和n2，首先求n1和n2的最小值d，然后依次检验d，d-1，d-2，….，1是否是n1和n2的公约数，这样找到的第一个公约数就是最大公约数。
代码实现：
import javax.swing.JOptionPanepublic class test{ public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:") int num1 = Integer.parseInt(num1String)
String num2String = JOptionPane.showInputDialog("Please enter the second integer:") int num2 = Integer.parseInt(num2String) int d if(num1<num2)
d=num1 else
d=num2 while(d>=1){ if(num1%d==0 &&num2%d==0) break
d--
}
JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",num1,num2,d))
}
}
