质数

abensyl · 2023-04-30 17:47:09 · 算法·理论

质数的定义

质数，又称素数。

质数和合数是针对所有大于 1 的 “自然数” 来定义的（所有小于等于 1 的数都不是质数）。
所有小于等于 1 的整数既不是质数也不是合数。
质数和素数都是同一种性质，只是叫法不同。

质数的判定

试除法

说明：d|n 代表的含义是 d 能整除 n（这里的 | 代表整除）。

一个合数的约数总是成对出现的，如果 d|n，那么 (n/d)|n，因此我们判断一个数是否为质数的时候，只需要判断较小的那一个数能否整除n就行了，即只需枚举 d\leq {n\over d}，即 d \times d\leq n，d\leq\sqrt n 就行了。

时间复杂度：O(\sqrt n)。

分解质因数

特别注意：分解质因数与质因数不一样！分解质因数是一个过程，而质因数是一个数。

基本定理：

一个合数分解而成的质因数最多只包含一个大于 \sqrt n 的质因数（反证法，若n可以被分解成两个大于 \sqrt n 的质因数，则这两个质因数相乘的结果大于 n，与事实矛盾）。
当枚举到某一个数 i 的时候，n 的因子里面已经不包含 2\sim i-1里面的数，如果 n\bmod i=0，则 i 的因子里面也已经不包含 2\sim i-1 里面的数，因此每次枚举的数都是质数。

唯一分解定理

算数基本定理（唯一分解定理）：任何一个大于 1 的自然数 n ，如果 n 不为质数，那么 n 可以唯一分解成有限个质数的乘积：

n={P_1}^{a_1}\times{P_2}^{a_2}\times\dots{P_n}^{a_n}

这里 {2\leq P_1<P_2<P_3\dots \leq P_n} 均为质数，其中指数 a_i 均是正整数。

这样的分解称为 n 的标准分解式。最早证明是由欧几里得给出的，由陈述证明。

此定理可推广至更一般的交换代数和代数数论。

质因子（质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

从质因子角度定义素数

两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。

只有一个质因子的正整数为质数。

筛质数

暴力筛法

对每个数，进行试除枚举，每次枚举时间复杂度为 O(\sqrt n)，总时间复杂度 O(n \sqrt n)。

朴素筛法

做法：把 2\sim(n-1) 中的所有的数的倍数都标记上，最后没有被标记的数就是质数。

原理：假定有一个数 p 未被 2\sim(p-1) 中的数标记过，那么说明，不存在 2\sim(p-1) 中的任何一个数的倍数是 p，也就是说 p 不是 2\sim(p-1) 中的任何数的倍数，也就是说 2\sim(p-1) 中不存在 p 的约数，因此，根据质数的定义可知：p 是质数。

补充：调和级数：调和级数是由调和数列各元素相加所得的和。中世纪后期的数学家 Oresme 证明了所有调和级数都是发散于无穷的。但是调和级数的拉马努金和存在，且为欧拉常数（以下公式中，c 就是欧拉常数，约等于 0.5772156649）。

c=\lim_{n\rightarrow +\infty}(1+{1\over 2}+{1\over 3}+\dots+{1\over n}-\ln n)

所以该算法的时间复杂度约为 O(n \log n)。

埃氏筛

埃拉托色尼筛法是由古希腊人埃拉托色尼在公元 250 年发明的质数筛法，简称埃式筛。

质数定理：1\sim n 中有 n\over \ln n个质数。

过程

① 先把 1 删除；
② 读取数列中当前最小的数2，再把2的倍数删除；
③ 读取数列中当前最小的数3，再把3的倍数删除；
④ 依次进行下去，直到把所求范围内的数均读取完。

时间复杂度：

由定理可知，1\sim n 中有 n\over \ln n个质数；

又 \lim\limits_{k\rightarrow +\infty}n + \frac n 2 + \frac n 3 + \dots + \frac n k = n\ln n；
总复杂度为 $O(n\log(\log n))$。

代码

bool a[N];
vector<int> prime;
void chkprime(int x) {
    for(int i=2;i<=x;++i) a[i]=true;
    for(int i=2;i<=x;++i)
        if(a[i]) {
            prime.push_back(i);
            for(int j=i*2;j<=x;j+=i)
                a[j]=false;
        }
}

4. 欧拉筛

时间复杂度：O(n)。

核心：1\sim n 内的所有合数 p 只会被其最小质因子筛掉。

原理：1\sim n 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的。

过程

对于每个数字，如果在遍历前未被标记过，则这个数字是质数。

对于所有数字（无论是质数还是非质数），都与现在已知的所有质数相乘，直到将要与他相乘的素数大于其最小质因子或所有素数都被乘完为止。

欧拉筛法（n=50 时筛选过程）：

:-: | :-: | :-: 2 | $\{2\}$ | $\{4\}

3 | \{2,3\} | \{6,9\} 4 | \{2,3\} | \{8\} 5 | \{2,3,5\} | \{10,15,25\} 6 | \{2,3,5\} | \{12\} 7 | \{2,3,5,7\} | \{14,21,35,49\} 8 | \{2,3,5,7\} | \{16\} 9 | \{2,3,5,7\} | \{18,27\} 10 | \{2,3,5,7\} | \{20\} 11 | \{2,3,5,7,11\} | \{22,33\} 12 | \{2,3,5,7,11\} | \{24\} 13 | \{2,3,5,7,11,13\} | \{26,39\} 14 | \{2,3,5,7,11,13\} | \{28\} 15 | \{2,3,5,7,11,13\} | \{30,45\} 16 | \{2,3,5,7,11,13\} | \{32\} 17 | \{2,3,5,7,11,13,17\} | \{34\} 18 | \{2,3,5,7,11,13,17\} | \{36\} 19 | \{2,3,5,7,11,13,17,19\} | \{38\}

\dots\ \dots\ \dots\ \dots

代码

const int N = 1e7+5;
bitset<N> f;
vector<int> prime;
void euler(int n) {
    for(int i=2;i<=n;++i) {
        if(!f[i]) prime.push_back(i);
        for(auto c:prime) {
            if(i*c>n) break;
            f[i*c]=1;
            if(i%c==0) break; 
        }
    }
    for(auto c:prime) cout<<c<<' ';
}