公约数（也叫公因数）｜公倍数｜小知识｜Golang

一、最大公约数（也叫公因数）

两个数的 最大公约数 是能够被两个数整除的最大正整数。

举例： 3 和 6 的最大公约数是3。“6和3的最大公因数是3。 6的因数有1,2,3,6，3的因数有1,3。两个数的最大公约数是能够被两个数整除的最大整数。

1071和462的最大公约数（也叫公因数）为21。

公因数和公约数只是叫法上的区别。两个数的最小公约数为1。

如何求？

辗转相除法：

以a=1071，b=462为例

首先取a，b中的最大值，假设最大值为a。首先用a减去b，一直减，减到当前的a小于b了。即a = 1071-462-462 = 147 < 462。此时我们要用b来减a了，停止条件也是b小于当前的a。那么就是b - a = 462 - 147 - 147 -147 = 21 < a。现在b = 21，a等于147。我们继续用大的减去小的， 147 - 21 .-.(7个21) - 21 = 0 。此时这个b即为他俩的最大公约数（公因数）

落实到编程中咋实现呢？

func gcd(a, b int) int { // 传入两个数 temp := 0 // 用来临时存放a-b的值 for b != 0 { // 终止条件是b==0 temp = a % b // a%b相当于 a一直减b，直到a小于b的时候的值 a = b // 这里为了方便一直用a%b，所以让ab的值互换了。此时的a为两个数中较大的 b = temp // b为 a%b的值 } return a // 当b==0的时候，也就是temp==0啊，那个时候被减数b就是最大公因子（公约数） }

1979. 找出数组的最大公约数

// 1.先找出最大值和最小值 // 2.然后用辗转相除法求得最大公约数就可以了  func findGCD(nums []int) int { min, max := nums[0], nums[0] for _, v := range nums { if v > max { max = v } if v < min { min = v } } return gcd(max, min) } func gcd(a, b int) int { temp :=0 for b != 0 { temp = a % b a,b = b, temp } return a }

2427. 公因子的数目

func commonFactors(a int, b int) int { ans := 0 for i:=1;i<=1000;i++{ // 由于数据规模不大，直接遍历 if a % i == 0 && b % i == 0 { // a、b同时可以取模一个数字且余数为0，此时的i就是一个 ans++ } } return ans }

二、公倍数

公倍数(common multiple)是指在两个或两个以上的自然数中，如果它们有相同的倍数，这些倍数就是它们的公倍数。公倍数中最小的，就称为这些整数的最小公倍数（lowest common multiple）。注意：没有最大公倍数的说法。
举例：求4和6的最小公倍数。

解答过程如下： 4=2×2，6=2×3。最小公倍数=2×2×3=12

如何求两个数的最小公倍数呢？

我们用：（借助辗转相除法），比较方便，因为前面求公约数就用的辗转相除法，方便一起记忆。

已知a和b两个数，最小公倍数 = （a*b）/ 最大公约数

如：4和6的最大公约数是2，那最小公倍数就是（4*6） / 2 = 12。因为两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积。

那么转换成代码就很好写了，把上面的辗转相除法求公约数的函数写出来，然后a*b除以这个公约数就可以咯。

package main import "fmt" func main() { a := 4 b := 6 fmt.Println("4和6的最大公约数为:", gcd(a, b)) fmt.Println("4和6的最小公倍数为:", 1, "两个数的最小公约数不用计算,是1 \n") // 求a和b的最小公倍数只要 a*b/它俩最大公约数 就可以了 fmt.Println("4和6的最小公倍数为:", a*b/gcd(a, b)) fmt.Println("4和6的最大公倍数为:", "Error:两个数没有最大公倍数(∞)") } func gcd(a, b int) int { temp := 0 for b != 0 { temp = a % b a = b b = temp } return a } // output 4和6的最大公约数为: 2 4和6的最小公倍数为: 1 两个数的最小公约数不用计算,是1 4和6的最小公倍数为: 12 4和6的最大公倍数为: Error:两个数没有最大公倍数(∞) // 暴力做法 func main() { // 求4, 6 的最小公倍数 a, b := 4, 6 ans := make([]int, 0) for i := 0; i < 5; i++ { ans = append(ans, a) a += 4 ans = append(ans, b) b += 6 } sort.Ints(ans) for i := 0; i < len(ans)-1; i++ { if ans[i] == ans[i+1] { fmt.Println(ans[i]) break } } }

如何求三个数的最小公倍数呢？

思路：算了暴力把。

func main() { // 求6 10 15的最小公倍数 a, b, c := 6, 10, 15 ans := make([]int, 0) for i := 0; i < 5; i++ { ans = append(ans, a) a += 6 ans = append(ans, b) b += 10 ans = append(ans, c) c += 15 } sort.Ints(ans) for i := 0; i < len(ans)-1; i++ { if ans[i] == ans[i+1] { fmt.Println(ans[i]) break } } }

其它... 算了算了，遇到再说把

今天的文章公约数（也叫公因数）｜公倍数｜小知识｜Golang分享到此就结束了，感谢您的阅读。

公约数（也叫公因数）｜公倍数 ｜小知识｜Golang

一、最大公约数（也叫公因数）

1979. 找出数组的最大公约数

2427. 公因子的数目

二、公倍数

相关推荐

公约数（也叫公因数）｜公倍数｜小知识｜Golang