素数及唯一分解定理

什么是素数

在信息学竞赛所涉及的数学领域里，素数（也叫质数）是一类非常关键的数。一个大于 1 的自然数，要是除了 1 和它自身之外，无法被其他自然数整除，那么这个数就被定义为素数。例如 2、3、5、7、11 等都是素数。与之相对，若一个大于 1 的自然数除了 1 和它自身外，还能被其他自然数整除，这样的数就被称作合数。像 4 能被 2 整除，6 能被 2 和 3 整除，所以 4 和 6 是合数。而 1 既不属于素数，也不属于合数。

唯一分解定理及其证明

唯一分解定理内容

唯一分解定理，也被叫做算术基本定理。该定理表明，任何一个大于 1 的自然数 $N$，如果 $N$ 不是素数，那么 $N$ 可以唯一地分解成有限个素数的乘积，即 $N = p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$，这里 $p_1 < p_2 < \cdots < p_n$ 均为素数，并且指数 $a_i$ 是正整数。例如 $60 = 2^2\times3^1\times5^1$，这种分解形式是唯一的。

证明思路

1. 存在性证明： 可以采用数学归纳法来证明任何大于 1 的自然数都能分解成素数的乘积。

• 当 $n = 2$ 时，$2$ 本身就是素数，分解形式为 $2^1$，满足分解成素数乘积的形式。
• 假设对于所有小于 $n$ 的自然数都能分解成素数的乘积。若 $n$ 是素数，那么 $n$ 本身就是一种素数分解形式；若 $n$ 是合数，那么 $n$ 可以写成 $n = a\times b$，其中 $1 < a,b < n$。根据归纳假设，$a$ 和 $b$ 都能分解成素数的乘积，所以 $n$ 也能分解成素数的乘积。

2. 唯一性证明： 假设存在一个大于 1 的自然数 $N$，它有两种不同的素数分解形式 $N = p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}=q_1^{b_1}q_2^{b_2}\cdots q_m^{b_m}$。因为 $p_1\mid N$，所以 $p_1\mid q_1^{b_1}q_2^{b_2}\cdots q_m^{b_m}$，根据素数的性质，$p_1$ 必定等于某个 $q_j$。不妨设 $p_1 = q_1$，那么等式两边同时除以 $p_1$，得到 $p_1^{a_1 - 1}p_2^{a_2}\cdots p_n^{a_n}=q_1^{b_1 - 1}q_2^{b_2}\cdots q_m^{b_m}$。重复这个过程，最终可以证明两种分解形式是完全相同的，即分解是唯一的。

怎么判断素数（附带例题及代码）

暴力判断法

原理

对于一个数 $n$，从 2 开始到 $\sqrt{n}$ 进行遍历，如果 $n$ 能被其中任何一个数整除，那么 $n$ 就不是素数，否则 $n$ 是素数。这是因为如果 $n$ 有一个大于 $\sqrt{n}$ 的因数 $a$，那么必然存在一个小于 $\sqrt{n}$ 的因数 $b=\frac{n}{a}$。

例题

题面：给定一个整数 $n$，判断它是否为素数。 输入输出样例：

• 输入：一个整数 $n$。 示例输入：

7

• 输出：如果 $n$ 是素数，输出 Yes，否则输出 No。 示例输出：

Yes

代码实现

#include <iostream>
using namespace std;
 
const int N = 1000010;
bool st[N];  // 标记数组，true 表示合数，false 表示素数
 
// 埃氏筛法求素数
void primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            cout << i << " ";
            for (int j = i + i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}
 
int main() {
    int n;
    // 读入一个整数
    cin >> n;
    primes(n);
    return 0;
}    

例题