质因数分解

数学与数论

说明

逐个试除到平方根；剩余大于 1 的数本身为质因子。

分析

从小质因子开始反复试除，找到一个因子就持续除尽对应幂次。试除到平方根后，若剩余值大于 1，它必然是最后一个质因子。

图解推演

84 先除以 2 两次变为 21，再除以 3 得 7。剩余 7 大于 1 且不再有不超过平方根的因子，因此输出 [2,2,3,7]。平方根界限应随着剩余数缩小；极大整数用 d≤n/d 比直接 d*d 更容易避免乘法溢出。

查看图表代码

适用前提与边界

示例返回带重复次数的因子列表；非常大的整数通常需要更先进的分解算法。

示例输入与调用

fmt.Println(Factors(84))

运行输出

[2 2 3 7]

完整 Go 示例

package main

import "fmt"

func Factors(n int) []int {
	out := []int{}
	for p := 2; p <= n/p; p++ {
		for n%p == 0 {
			out = append(out, p)
			n /= p
		}
	}
	if n > 1 {
		out = append(out, n)
	}
	return out
}

func main() {
	fmt.Println(Factors(84))
}