分解质因数

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()
}