最大公约数及最小公倍数是个什么东西-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

最大公约数及最小公倍数是个什么东西

简介: 源码地址 import java.util.Scanner; /** * @author cc ******************************************************************** * 1)最大公约数(最大公因数)就是几个数公有的因数中最大的一个。例12与18 12的因数有1,12,2,6,3,4



源码地址


import java.util.Scanner;

/**
 * @author cc
 ******************************************************************** 
 *         1)最大公约数(最大公因数)就是几个数公有的因数中最大的一个。例12与18 12的因数有1,12,2,6,3,4
 *         18的因数有1,18,2,9,6,3 公有的因数有1,2,3,6, 所以6就是12与18的最大公约数.
 * 
 *         2)最小公倍数就是几个数公有的倍数中最小的一个。 例4和6 4的倍数有4,8,12,16,20,24,……
 *         6的倍数有6,12,18,24,…… 4和6 公倍数 12,18……, 所以4和6的最小公倍数是12 。 源码地址
 *         http://yunpan.cn/QD8k8biec66uN
 ******************************************************************* 
 */
public class commonMultipleDivisor {
	/**
	 * 
	 * @param args
	 * 最小公倍数=两数的乘积/最大公约数
	 * 最大公约数=两数的乘积/最小公倍数
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a = 0, b = 0;
		int m;

		Scanner in = new Scanner(System.in);
		while (a <= 0 || b <= 0) {
			System.out.println(" 请一次输入两个非零正整数 \n");
			try {
				a = in.nextInt();
				b = in.nextInt();
			} catch (Exception e) {
			}
		}
		in.close();

		m = fun2(a, b);
		System.out.println("最大公约数为:" + m);
		System.out.println("最小公倍数为:" + (a * b) / m);
	}

	public static int fun1(int a1, int b1) {
		int c, temp;

		if (a1 < b1) {
			temp = a1;
			a1 = b1;
			b1 = temp;
		}
		c = a1 % b1;
		while (c > 0) {
			a1 = b1;
			b1 = c;
			c = a1 % b1;
		}
		return (b1);
	}

	/**
	 * 更相减损法
	 *  1.两个数都为偶数除2直到一个不为偶数
	 *  2.两数大的减小数,差与被减数进行大的减小的,直到差==被减数
	 *  3.第一步除了几次2,则用2的几次方*最后的差值 == 最大公约数
	 *  http://baike.baidu.com/link?url=ptGm72BthG_3TlM2GqkEAUhnsd15RFxMTMfHxlwAYXl2MobF1feLKepGyp6arNxw
	 */
	public static int fun2(int m1, int m2) {
		int n = 0;
		int temp = 0;
		while (m1 / 2 == 0 && m2 / 2 == 0) {
			m1 = m1 / 2;
			m2 = m2 / 2;
			n++;
		}
		while (m1 != m2) {
			if (m1 < m2) {
				m2 = m2 - m1;
			} else {
				m1 = m1 - m2;
			}
		}
		if (0 != n) {
			temp = 2 ^ n * m1;
		} else {
			temp = m1;
		}
		return temp;
	}

}









版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: