题解 | 质数因子

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func getPrimeFactor(num int) []int {
    var resSlice []int
    if num <= 2 {
        return []int{num}
    } else {
        originNum := num
        for i := 2; i <= int(math.Sqrt(float64(originNum))); i++ {
            if num % i == 0 {
                for {
                    if num % i == 0 {
                        resSlice = append(resSlice, i)
                        num = num / i
                    } else {
                        break
                    }
                }
                 
            }
            
        }
        if num > 1 {
            resSlice = append(resSlice, num)
        }
        // 一种极端情况，非常大的质数，只有一个数字
        if resSlice == nil {
            resSlice = []int{num}
        }
    }
    return resSlice
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    if scanner.Scan() {
        var input int
        input, err := strconv.Atoi(scanner.Text())
        if err != nil {
            fmt.Println(err)
        }
        res := getPrimeFactor(input)
        for _, v := range res {
            fmt.Printf("%d ", v)
        }
    }
    
}

判断一个质数是否能够组成数字n的质因子的方法就是直接计算余数是否为0，若为0表示是质因子，因此直接取模运算即可。但如果最大数判断为n本身，对于很多测试用例会超时，因此可以判断到根号n，如果还剩余了大于1的未被分解的数，那么这个数就是最后一个质因子。原理是按理说枚举到某个数时能够得到a * b = n，a<b，那么必然存在a*a<n,也就是说只要平方超过n，那么就是最大的数，除非本身就是一个质数，推断如下：

假设n是一个正整数，并且存在两个正整数 a 和 b ，使得n = a * b。不妨设 a < b，那么有a * a < a* b = n ，即 a^2 = n ，进一步可得 a = √n￣。

这意味着如果n有一个大于 √n￣ 的因子b，那么必然存在一个小于等于√n￣的因子a与之对应，因为 n = a*b 。所以，我们在寻找n 的质因子时，只需要检查从2到√n￣（向下取整）的所有整数即可。如果在这个范围内没有找到n 的因子，那么 n本身就是一个质数。