【蓝桥云课】最大公约数与最小公倍数

原标题:【蓝桥云课】最大公约数与最小公倍数

一、最大公约数gcd(a,b)

引例:

a=24,其因子有1、2、3、4、6、8、12、24
b=15,其因子有1、3、5、15
最大公约数gcd(a,b)文章来源地址https://www.yii666.com/blog/63042.html=gcd(24,15)=3

欧几里得辗转算法:

a = max(a,b);
b = min(a,b);
while(b>0){
	t = a%b;
	a = b;
	b = t;
}

运算过程:

a = 24, b = 15
1) t = 24%15 = 9,a = 15,b = 9;
2) t = 15%9 = 6, a = 9, b = 6;
3) t= 9%6 =3, a = 6, b = 3;
4) t = 6%3 = 0, a = 3, b = 0;
b>0条件不满足,while循环停止。

在这里插入图片描述

程序代码:

import java.util.Scanner;
文章来源站点https://www.yii666.com/public class Test{
	public static void main(String[] args){
		int a = 0, b = 0;
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			www.yii666.coma = sc.nextInt();
			b =www.yii666.com sc.nextInt();
			System.out.println("欧几里得" + gcd_1(a,b));
			System.out.println("递归" + gcd_2(a,b));
		}
	}
	public static int gcd_1(int a, int b){
		while(b>0){
			int temp = a%b;
			a = b;
			b = t;//gcd(a,b)=>gcd(b,a%b);
		}
		return a;
	}
	public static int gcd_2(int a, int b){
		return b==0?a:gcd_2(b, a%b);
	}
}

二、最小公倍数lcm(a,b)

L C M ( a , b ) = a ∗ b g 文章来源地址https://www.yii666.com/blog/63042.html c d ( a , b ) LCM(a,b)=\frac{a*b}{gcd(a,b)} LCM(a,b)=gcd(a,b)ab

来源于:【蓝桥云课】最大公约数与最小公倍数

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

领支付宝红包赞助服务器费用

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png