锐客网

  1. 首页 > it技术 > >

求解最大公约数，最小公倍数（Java语言实现）


Java代码实现

  • 一、求最大公约数
      • （1）辗转相除法实现（method of successive division）
      • （2）辗转相减法实现（Rolling subtraction）
      • （3）穷举法实现
  • 二、求最小公倍数（least common multiple）

有一个公式记住：a*b=最小公倍数 x 最大公约数
一、求最大公约数 （1）辗转相除法实现（method of successive division）
【求解最大公约数，最小公倍数（Java语言实现）】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

（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

程序样例运行结果
求解最大公约数，最小公倍数（Java语言实现）
文章图片

文章编辑于
2019年4月2日23:52:03

    推荐阅读


    上一篇：听马士兵讲redis笔记三 redis 持久化RDB fork copy_on_write

    下一篇：电路设计|GSM模块_GSM设备和网络错误代码