分解质因数

package main

import (
	"fmt"
	"math/big"
)

// primeFactors 函数用于计算给定大整数 n 的所有质因数，并将它们存储在一个切片中返回。
func primeFactors(n *big.Int) []*big.Int {
	factors := []*big.Int{} // 用于存储质因数的切片

	// 从最小素数 2 开始，逐渐递增检查直到 p*p 大于 n
	p := big.NewInt(2)
	for new(big.Int).Mul(p, p).Cmp(n) <= 0 {
		// 如果 n 能整除 p，则 p 是 n 的一个质因数
		if n.Mod(n, p).Sign() == 0 {
			// 计算 p 的最大幂，同时更新 n
			exp := big.NewInt(0)
			for n.Mod(n, p).Sign() == 0 {
				n.Div(n, p)
				exp.Add(exp, big.NewInt(1))
			}

			// 将 p 的最大幂添加到因子列表中
			for i := 0; i < exp.Int64(); i++ {
				factors = append(factors, new(big.Int).Set(p))
			}
		}
		p.Add(p, big.NewInt(1)) // 尝试下一个素数
	}

	// 如果 n 是一个大于 1 的素数，则 n 是一个质因数
	if n.Cmp(big.NewInt(1)) > 0 {
		factors = append(factors, n)
	}

	return factors // 返回计算得到的质因数切片
}

func main() {
	// 创建大整数 n
	n := new(big.Int).SetInt64(1041601901437367792339)

	// 调用 primeFactors 函数计算 n 的所有质因数
	factors := primeFactors(n)

	// 打印 n 的所有质因数
	fmt.Printf("Prime factors of %d are: ", n)
	for _, factor := range factors {
		fmt.Printf("%d ", factor)
	}
	fmt.Println()
}