最小公倍数和最大公约数的问题

2020-03-30

一、求两个数最小公倍数的问题

主要思路：设两个数分别为a、b,首先两个数的最大公约数为a×b,最小公倍数的范围一定是Max(a,b)到a×b之间，所以用for循环来判断当一个数同时对a和b求余都等于0时，那么这个数一定是最小公倍数。

源代码：

import java.util.Scanner;

public class Min_gongbeishu {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int min = a > b ? a : b;
		int max = a * b;
		for (int i = min; i <= max; i++) {
			if (i % a == 0 && i % b == 0) {
				System.out.println("最小公倍数为" + i);
				break;
			}
		}

	}

}

二、求两个数最大公因数的问题

最大公因数问题与上相反，选出较小的一个数开始自减，让a和b同时对这个数求余等于0时，这个数为最大公因数。

源代码：

import java.util.Scanner;

public class Max_gongyinshu {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int min = a < b ? a : b;
		for (int i = min; i >= 1; i--) {
			if (a % i == 0 && b % i == 0) {
				System.out.println("最大公约数是：" + i);
				break;
			}
		}

	}

}

另外补充两个数交换值的方法

方法一(引入中间变量)

1
2
3

int c=a;
    a=b;
    b=c;

方法二(相减法)

1
2
3

a=a+b;
b=a-b;
a=a-b;

方法三(异或法)

1
2
3

a = a^b;
b = a^b;
a = a^b;

异或法基于以下几个性质：

任意变量x与自身异或结果为0，即：x^x = 0
任意变量x与0进行异或运算，结果不变，即：x^0 = x
异或运算的结合性：a^b^c = (a^b)^c = a^(b^c)
异或运算的交换性：a^b = b^a

详解：

1
2
3

a = a^b 
b = a^b --> b = (a^b)^b = a^(b^b) = a^0 = a       //完成了a的值交给b的过程。 
a = a^b --> a = (a^b)^a = (b^a)^a = b^(a^a) = b^0 = b       //完成了b的值交给a的过程。

本文作者： nowfitness
本文链接： https://www.nowfitness.top/archives/5dd25dfa.html
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！