【数学】分解质因数

题目

867. 分解质因数

---

给定 $n$ 个正整数 $a_i$ ，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含一个正整数 $a_i$ 。

输出格式

对于每个正整数 $a_i$ ，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

$1 \le n \le 100$ ,
$2 \le a_i \le 2 \times 10^9$

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

解题

方法一：试除法

前置

质因数分解（Prime Factorization）

是将一个合数写成几个质数相乘的形式，其中每个质数都是这个合数的因数。例如 $45=3^2 \times 5$ 。根据算术基本定理，这样的分解结果应该是独一无二的。

测试样例解释

输入两个数：$6$ 、 $8$，分解质因数：$6=2^1 \times 3^1$，$8 = 2^3$。

所以对于 $6$ 输出：

2 1
3 1

对于 $8$ 输出：

2 3

思路

朴素解法

若要将数 $n$ 进行质因数分解，从小到大（$2 \dots n$）枚举 $n$ 的所有因数，求出该因数的次数，输出该因数与其次数。
由以上思路可以写出如下代码：

void pf(int n) {
    for (int i = 2; i <= n; ++i) {
        // 枚举因数
        if (n % i == 0) {
            int s = 0;
            // 求次数
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            System.out.println(i + " " + s);
        }
    }
}

我们需要分解质因数，但枚举的 i 是所有因数而不是质因数，如何证明 i 在 n % i == 0 成立时一定是质因数？
——反证法：假如 i 是一个合数，那么它一定也可以分解成多个质因子相乘的形式，而此时 i 是 n 的因子成立，所以这多个质因子既是 i 的质因子又 n 的质因子并且比 i 要小，而比 i 小的数在之前的循环过程中一定是被条件除完了的，也就是说质因子的个数是 $0$，此时产生了矛盾，所以 i 不可能是合数，只可能是质数。

优化

有性质：$n$ 中最多只包含一个大于等于 $\sqrt{n}$ 的质因子。（易证：若 $n$ 可以被分解成两个大于$\sqrt{n}$ 的质因数，则这两个质因数相乘的结果大于 $n$ ，与事实矛盾）

所以枚举的时候可以只枚举 $\le \sqrt{n}$ 的因数，最后剩下的 $n$ 如果大于 $1$，那么剩下的 $n$ （循环过程中 $n$ 会变）就是那个大于等于 $\sqrt{n}$ 的质因子。

代码

import java.util.*;
import java.io.*;

public class Main {
    static void pf(int n) {
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    ++s;
                }
                System.out.println(i + " " + s);
            }
        }
        if (n > 1) System.out.println(n + " 1");
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            pf((int) in.nval);
            System.out.print("\n");
        }
    }
}

#include <iostream>

using namespace std;

void pf(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            printf("%d %d\n", i, s);
        }
    }
    if (n > 1) printf("%d 1\n", n);
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a;
        scanf("%d", &a);
        pf(a);
        puts("");
    }
    
    return 0;
}

时间复杂度：$O(\log{N})$（最好） $O(\sqrt{n})$（最坏）。