求解最大公约数,最小公倍数(Java语言实现)
2023-04-18 14:50:54 时间
Java代码实现
有一个公式记住:a*b=最小公倍数 x 最大公约数
一、求最大公约数
(1)辗转相除法实现(method of successive division)
java代码实现,不管a,b的大小,结果都是一样的
public static int division(int a,int b) {
while(a % b!=0) {//直到余数为0 ,最大公约数为上一步的余数
temp= a%b;
a = b;
b = temp;
}
return b;
}
(2)辗转相减法实现(Rolling subtraction)
//Rolling subtraction
//辗转相减法
public static int substract(int a,int b) {
while(true) {
if(a>b) {
a=a-b;
}else if(a<b) {
b=b-a;
}else {
return a;//这里返回a,b都可以,因为最终a是等于b的
}
}
}
(3)穷举法实现
通过循环,将两个数中任意一个数定义为循环起点“i”,然后将每循环一次,进行一次判断,当a和b中的两个数同时对循环元素i取余,满足条件的 “i” 即为最大公约数
//穷举
public static int Exhaus(int a,int b) {
for(int i=a;;i--)
if(a%i==0 && b%i==0)
return i;
}
二、求最小公倍数(least common multiple)
前面讲过的,a*b=最大公约数 x 最小公倍数,这下你就清楚了吧 这里我们直接把前面的代码拿过来
int leastCommonMultiple=(a*b)/Exhaus(a,b);
本次内容分享的全部代码
import java.util.Scanner;
/**
* @author gorit
* @date 2019年4月2日
* 最大公约数以及最小公倍数的实现
* */
public class greatestCommonDivisor {
static int temp;//定义一个全局的中间变量
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int b=in.nextInt();
System.out.println(a+"和"+b+"的辗转相除法得到的结果为:"+division(a, b));
System.out.println(a+"和"+b+"的辗转相减法得到的结果为:"+substract(a, b));
System.out.println(a+"和"+b+"的穷举法得到的结果为:"+Exhaus(a, b));
System.out.println(a+"和"+b+"的最小公倍数为:"+(a*b)/Exhaus(a, b));
}
//method of successive division
//辗转相除法的实现
public static int division(int a,int b) {
while(a % b!=0) {//直到余数为0 ,最大公约数为上一步的余数
temp= a%b;
a = b;
b = temp;
}
return b;
}
//Rolling subtraction
//辗转相减法
public static int substract(int a,int b) {
while(true) {
if(a>b) {
a=a-b;
}else if(a<b) {
b=b-a;
}else {
return b;//这里返回a,b都可以,因为最终a是等于b的
}
}
}
//穷举
public static int Exhaus(int a,int b) {
for(int i=a;;i--)
if(a%i==0 && b%i==0)
return i;
}
}
程序样例运行结果
文章编辑于 2019年4月2日23:52:03
相关文章
- JetBrains 官宣:2022.3 版本开始必须 Java 17!!
- Java学习-第一部分-第二阶段-第六节:泛型
- 接口回调与lambda表达式
- 【Java面试】这也太卷了~面试竟然问,HTTP协议和RPC协议的区别
- 同事写了一个责任链模式,bug 无数...
- 一天十道Java面试题----第一天(面向对象-------》ArrayList和LinkedList)
- JSP中的JSTL 标签库
- Java---Lambda
- JSP基础知识总结
- 【Java面试】准备跳槽!那这期面试题必须要会,请描述一下Redis的缓存淘汰策略
- 面试题:Java序列化与反序列化
- day26--Java集合09
- Java枚举简单介绍
- 图文详解 Java 泛型,写得太好了!
- 【Java面试】当任务数超过线程池的核心线程数时,如何让它不进入队列,而是直接启用最大线程数
- Java中的命名规则
- idea主类main左侧栏启动按钮消失原因
- 从new File("")到jdk源码
- java死锁(Java-level deadlock)
- day25--Java集合08