JAVA 求最小公因数
文章目录
- JAVA 求最小公因数
- 方法一：枚举法的第一种
- 方法一：枚举法的第二种
- 方法二：展转相除法(欧几里德算法)
- 方法三：递归
- 拓展 求最小公倍数公式为
- 综合 辗转相除法+递归 求n个数的最大公约数和最小公倍数
题目：任意输入两个整数，如何求他们的最大公约数？
最大公约数：也称最大公因数，最大公因子，是指两个或多个整数共有约数中最大的一个。
方法一：枚举法的第一种
先输入两个整数，然后比较两个数的大小，大的整数对小的整数求余，若不为0，则让小的整数-1，再继续前面的求余操作，直至最后跳出循环，输出最大公约数。
package CSDN.资料一;
import java.util.Scanner;
/*题目：任意输入两个整数，如何求他们的最大公约数？
*最大公约数：也称最大公因数，最大公因子，是指两个或多个整数共有约数中最大的一个。
* 方法一：枚举法
* 先输入两个整数，然后比较两个数的大小，大的整数对小的整数求余，若不为0，则让小的整数-1，再继续前面的求余操作，直至最后跳出循环，输出最大公约数。
*/
public class GreatestCommonDivisor01 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入第一个整数：");
int n = scanner.nextInt();
System.out.println("请输入第二个整数：");
int m = scanner.nextInt();
//x保存小的那个数
int x;
if(m>n){
x=n;
}else{
x=m;
}
//大的整数对小的整数求余，若不为0，则让小的整数-1
while(m%x!=0||n%x!=0){
x--;
}
System.out.println(x);
}
}
运行结果：
方法一：枚举法的第二种
package CSDN.资料二;
import java.util.Scanner;
/*
*枚举法
*/
public class GreatestCommonDivisor03 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入一个自然数");
int a = in.nextInt();
System.out.println("请再输入一个自然数");
int b = in.nextInt();
int gcd = 1;
for (int i = 2; i <=a&&i<=b ; i++) {
if(a%i==0&&b%i==0){
gcd = i;
}
}
System.out.println(a+"和"+b+"的最大公约数是"+gcd);
}
}
方法二：展转相除法(欧几里德算法)
辗转相除法： gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
如果要用辗转相除法求几个数的最大公约数，能够先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是全部这些数的最大公约数。
package CSDN.资料二;
import java.util.Scanner;
/*
* 展转相除法(欧几里德算法)
*/
public class GreatestCommonDivisor04 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入一个自然数");
int a = in.nextInt();
System.out.println("请再输入一个自然数");
int b =in.nextInt();
int oa = a;
int ob = b;
while(b!=0){
int r = a%b;
a=b;
b=r;
}
System.out.println(oa+"和"+ob+"的最大公约数是"+a);
}
}
将上述的方法二封装成方法
package CSDN.资料三.封装成方法;
import java.util.Scanner;
public class GreatestCommonDivisor05 {
public static void main(String[] args) {
int a = 0,b=0;
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
a =sc.nextInt();
b=sc.nextInt();
System.out.println("欧几里得："+gcdWhile(a,b));
}
}
public static int gcdWhile(int a,int b){
while(b>0){
int temp = a%b;
a=b;
b=temp;
}
return a;
}
}
方法三：递归
package CSDN._03资料三.封装成方法.递归;
import java.util.Scanner;
public class GreatestCommonDivisor06 {
public static void main(String[] args) {
int a = 0,b=0;
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
a =sc.nextInt();
b=sc.nextInt();
System.out.println("递归1："+gcdRecursion1(a,b));
System.out.println("递归2："+gcdRecursion2(a,b));
}
}
public static int gcdRecursion1(int a,int b){
return b==0?a:gcdRecursion1(b,a%b);
}
public static int gcdRecursion2(int a,int b){
if(a%b==0){
return b;
}else{
return gcdRecursion2(b,a%b);
}
}
}
拓展 求最小公倍数公式为
LCM（a ，b） = (a * b) / gcd(a,b)
即 最小公倍数 = 两数之积 / 两数的最大公约数
综合 辗转相除法+递归 求n个数的最大公约数和最小公倍数
package CSDN._04资料四;
import java.util.Scanner;
public class GETGCDByHHH {
// 最大公约数
static int getGCD(int a, int b) {
if (b == 0)
return a;
return getGCD(b, a % b);
}
// 最小公倍数
static int getLCM(int a, int b) {
return a * b / getGCD(a, b);
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("要输入几个数字 : ");
int n = sc.nextInt();
int[] data = new int[n];
for (int i = 0; i < n; i++) {
System.out.println("请输入第"+(i+1)+"数");
data[i] = sc.nextInt();
}
int gcd = data[0];
for(int i = 1; i < n; ++i){
gcd = getGCD(data[0], data[i]);
}
int lcm = 1;
for (int i = 1; i < n; i++) {
lcm = getLCM(data[0],data[i]);
}
System.out.println("最大公约数是：" + gcd);
System.out.println("最小公倍数是：" + lcm);
}
}
