唯一分解定理

唯一分解定理

1.内容

任何一个大于1的整数n都可以分解成若干个质数的连乘积，如果不计各个质数的顺序，那么这种分解是惟一的，即若n>1，则有$$n=\prod p_i^j$$这里的$p_i$是质数。

可以进行简单证明，假设$p_i$是合数，那么它可以接着分解为两个数相乘的形式，所以最后$p_i$一定是质数。

2.唯一分解定理模板代码

模板代码其实也是唯一分解定理的直接应用，给一个整数n，问有多少个质数是n的约数。这里就需要进行分解，也就是用到了唯一分解定理，我们直接上代码，然后逐一解释难懂的地方。

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long n = scanner.nextLong();
    int ans = 0;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if(n%i==0) ans++;
        while(n%i == 0) {
            n = n / i;
        }
    }
    if(n > 1) {
        ans++;
    }
    System.out.println(ans);
}
}

1. 一般n可能给的很大，注意最好用long类型

2. 我们如果要求一个数的因数，会从1开始遍历进行试除，那么应该遍历到哪里呢？是n吗？其实遍历到$\sqrt{n}$就可以了。因为如果找到了一个因子为a，那么大于$\sqrt{n}$的另一个因子就是n/a

3. 很明显这个for循环我们是在采用试除法来求n的因子，但是我们如何保证求到的因子是质因子呢？这就是里面的while循环的作用了。给大家举个例子，n=36，6是它的因子，但是不是质因子，那么我们会不会遍历到它呢？i=2时，在while循环里就把36里的所有2都除没了，此时n=9。i=3时，在while循环里就把36里的所有3都除没了，此时n=1。那么此时的n里面已经不包含6了，因为6是由2和3构成的，在遍历到6之前，n里的所有的2和3都没有了，自然也就没有6了。这就是while循环的作用，他保证了我们找到的因子一定是质数

4. 最后一个地方，为什么在代码的最后要加一个if判断呢？还是给大家举一个例子，比如n=396，i=2时，n=99。n=3时，n=11。当i=4时i>$\sqrt{n}$，所以for循环退出了。但是你也可以发现，11也是n的一个质因子，所以我们在最后要判断一下，防止把这种情况漏了。