go语言：实现求 1 到 20 的所有数整除的最小正数算法（附带源码）
一、项目背景详细介绍
在数学与算法领域，有一类经典问题：
最小公倍数（Least Common Multiple, LCM）问题
其中最著名的经典题之一是：
找到能够被 1 到 20 所有整数整除的最小正数
这也是：
👉 Project Euler 第5题
该问题看似简单，但背后涉及：
- 最大公约数（GCD）
- 最小公倍数（LCM）
- 欧几里得算法
- 数论优化
- 素因数分解
是学习数学算法的经典案例。
二、题目详细说明
2.1 题目定义
寻找最小正整数：
x满足：
x % 1 == 0 x % 2 == 0 x % 3 == 0 ... x % 20 == 0即：
👉 能被 1~20 所有整数整除。
2.2 示例（小规模）
例如：
1~10最小满足值：
2520因为：
2520 可以被： 1,2,3,4,5,6,7,8,9,10 全部整除2.3 最终答案（1~20）
结果：
232792560三、项目需求详细介绍
3.1 功能需求
实现函数：
func SmallestMultiple(n int) int功能：
- 输入 n
- 返回能被 1~n 全部整除的最小正整数
3.2 输入要求
n >= 13.3 输出要求
返回：
LCM(1,2,3...n)3.4 扩展需求
支持：
- 超大范围
- 大整数
- 多种算法实现
- 高性能优化
四、相关技术详细介绍
4.1 什么是最小公倍数（LCM）？
定义：
两个数共同倍数中的最小值例如：
LCM(4,6)=124.2 什么是最大公约数（GCD）？
定义：
两个数共同约数中的最大值例如：
GCD(12,18)=64.3 LCM 与 GCD 的关系（核心）
最重要公式：
LCM(a,b) = a*b / GCD(a,b)这是本题核心。
4.4 欧几里得算法（辗转相除法）
用于：
👉 快速求 GCD
公式：
GCD(a,b) = GCD(b, a%b)示例
GCD(48,18) 48%18=12 18%12=6 12%6=0 结果=6五、实现思路详细介绍
5.1 方法一：暴力法（不推荐）
思路：
从1开始：
不断检查： 是否能被1~20全部整除问题：
极其慢5.2 方法二：逐步LCM（推荐）
核心思想：
LCM(1,2,3...n) = LCM(LCM(1,2),3...)5.3 方法三：素因数分解优化
数学方法：
- 找每个素数最高幂
例如：
1~20: 2^4 3^2 5 7 11 13 17 19相乘即可。
六、完整实现代码
// =========================================== // file: main.go // 求1到20所有数整除的最小正数 // =========================================== package main import ( "fmt" "math" ) ////////////////////////////////////////////////////////////// // 欧几里得算法：求最大公约数 GCD ////////////////////////////////////////////////////////////// func GCD(a, b int) int { for b != 0 { a, b = b, a%b } return a } ////////////////////////////////////////////////////////////// // 求最小公倍数 LCM ////////////////////////////////////////////////////////////// func LCM(a, b int) int { return a * b / GCD(a, b) } ////////////////////////////////////////////////////////////// // 方法一：逐步LCM（推荐） ////////////////////////////////////////////////////////////// func SmallestMultiple(n int) int { result := 1 for i := 2; i <= n; i++ { result = LCM(result, i) } return result } ////////////////////////////////////////////////////////////// // 方法二：暴力法（演示） ////////////////////////////////////////////////////////////// func SmallestMultipleBrute(n int) int { number := n for { divisible := true for i := 1; i <= n; i++ { if number%i != 0 { divisible = false break } } if divisible { return number } number++ } } ////////////////////////////////////////////////////////////// // 判断素数 ////////////////////////////////////////////////////////////// func IsPrime(n int) bool { if n < 2 { return false } for i := 2; i <= int(math.Sqrt(float64(n))); i++ { if n%i == 0 { return false } } return true } ////////////////////////////////////////////////////////////// // 方法三：素因数优化法 ////////////////////////////////////////////////////////////// func SmallestMultiplePrime(n int) int { result := 1 for p := 2; p <= n; p++ { if IsPrime(p) { power := p for power*p <= n { power *= p } result *= power } } return result } ////////////////////////////////////////////////////////////// // 主函数 ////////////////////////////////////////////////////////////// func main() { n := 20 fmt.Println("LCM方法:") fmt.Println( SmallestMultiple(n), ) fmt.Println("素因数优化:") fmt.Println( SmallestMultiplePrime(n), ) // 暴力法仅适合小范围 fmt.Println("暴力法(1~10):") fmt.Println( SmallestMultipleBrute(10), ) }七、代码详细解读
7.1 GCD函数
作用：
👉 使用欧几里得算法求最大公约数
核心：
a, b = b, a%b7.2 LCM函数
作用：
- 求最小公倍数
公式：
LCM = a*b/GCD7.3 SmallestMultiple
作用：
👉 逐步累积LCM
过程：
LCM(1,2) → LCM(result,3) → LCM(result,4) ...7.4 SmallestMultiplePrime
作用：
👉 数学优化版本
核心：
取每个素数的最高幂7.5 SmallestMultipleBrute
作用：
- 演示暴力法
缺点：
非常慢八、项目详细总结
8.1 核心思想
本问题本质：
👉LCM连续累积问题
8.2 技术收获
你会掌握：
- GCD
- LCM
- 欧几里得算法
- 数论优化
8.3 性能分析
| 方法 | 时间复杂度 |
|---|---|
| 暴力法 | 极高 |
| LCM法 | O(n log n) |
| 素因数法 | O(n√n) |
8.4 最优方案
推荐：
LCM连续法工程最常用。
九、项目常见问题及解答
9.1 为什么 LCM 可以连续计算？
因为：
LCM满足结合律9.2 为什么暴力法慢？
因为：
👉 检查次数巨大。
9.3 为什么欧几里得算法快？
因为：
每次都会大幅缩小问题规模9.4 为什么素因数法有效？
因为：
👉 LCM 本质是：
所有素因数最高幂组合十、扩展方向与性能优化
10.1 大整数支持
使用：
math/big支持超大范围。
10.2 并行GCD
使用 goroutine。
10.3 分布式数论计算
适合科研级。
10.4 数学扩展
相关问题：
- 最大公约数合集
- 中国剩余定理
- 欧拉函数
10.5 工程应用
- 密码学
- 分布式哈希
- 时钟同步系统
结语
“1~20 最小整除数问题”是：
👉数论算法中的经典入门题
它帮助你真正理解：
- GCD 与 LCM 的关系
- 欧几里得算法的强大
- 数学优化如何替代暴力