【专题】质数筛

博客园   2023-08-13 06:17:05


(资料图片)

质数筛

Q:给定自然数 n ,求 [1, n] 区间内的所有质数。

1、原始筛法(时间复杂度:O(n√n)

算法思路:不加思考的暴力枚举,即逐个判断区间内每个数是否是质数。判断单个质数的时间复杂度为O(√n) ,判断 1 ~ n 是否是质数的时间复杂度为O(n√n)

代码展示:

int tot, prime[N]; /* prime[i] 为第 i 个质数 */bool is_prime(int n) {    if (n < 2) return false;    for (int i = 2; i * i <= n; i ++)        if (!(n % i))            return false;    return true;}void prime_sieve() {    for (int i = 1; i <= n; i ++)        if (is_prime(i))            prime[++ tot] = i;}

2、普通筛法(时间复杂度:O(n log n)

算法思路:和原始筛法相比有改进,一个(大于 1)自然数的 k 倍数(k > 1)都一定不是质数。

代码展示:

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数,false 即是 */int tot, prime[N]; /* 共有 tot 个质数,prime[i] 为第 i 个质数 */ void prime_sieve() {   for (int i = 2; i <= n; i ++){     if (!is_prime[i]) prime[++ tot] = i;     for (int j = i << 1; j <= n; j += i)       is_prime[j] = true;   } }

3、埃氏筛 形式 1(时间复杂度:O(n log logn)

算法思路:著名的质数筛法,由古希腊数学家 Eratosthenes(埃拉托斯特尼)发明,和普通筛法相比减少了许多冗余,一个质数的 k 倍数(k > 1)都一定不是质数。

代码展示:

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数,false 即是 */int tot, prime[N]; /* tot 个质数,prime[i] 为第 i 个质数 */void Eratosthenes_sieve() {    for (int i = 2; i <= n; i ++){        if (!is_prime[i]){            prime[++ tot] = i;            for (int j = i << 1; j <= n; j += i)                 is_prime[j] = true;        }    }}

4、埃氏筛 形式 2(时间复杂度:O(n log logn)

算法思路:埃氏筛的一种不明显的优化,大于 1 的整数的质数倍数不是质数。

代码展示:

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数,false 即是 */int tot, prime[N]; /* 共有 tot 个质数,prime[i] 为第 i 个质数 */ void Eratosthenes_sieve() {   for (int i = 2; i <= n; i ++){     if (!is_prime[i]) prime[++ tot] = i;     for (int j = 1; j <= tot && i * prime[j] <= n; j ++)       is_prime[i * prime[j]] = true;   } }

5、欧拉筛(时间复杂度:O(n)

算法思路:最著名、最常用的质数筛!在埃氏筛的形式 2 上多了一行神奇的代码,时间复杂度就从O(nlog logn)降至O(n) ,因其是线性复杂度,所以也称线性筛。如果已经被筛过了,则可以终止这轮筛选合数。

代码展示:

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数,false 即是 */int tot, prime[N]; /* 共有 tot 个质数,prime[i] 为第 i 个质数 */ void Linear_sieve() {   for (int i = 2; i <= n; i ++){     if (!is_prime[i]) prime[++ tot] = i;     for (int j = 1; j <= tot && i * prime[j] <= n; j ++){      is_prime[i * prime[j]] = true;                 if (!(i % prime[j])) break; // beautiful !!!           }  } }

5、埃氏筛 形式 1 + bitset(时间复杂度:O(n loglogn)

算法思路:令人难以置信的是,埃氏筛搭配 C++ 神奇的 bitset 容器(不是 STL),可以让高复杂度的它效率高于低复杂度的欧拉筛!!!

代码展示:

bitset is_prime; /* is_prime[i] 表示 i 是不是质数,true 即是 */int tot, prime[N]; /* tot 个质数,prime[i] 为第 i 个质数 */void Eratosthenes_sieve() {    is_prime.set(); /* 初始化为 true */    is_prime[0] = is_prime[1] = false;    for (int i = 2; i <= n; i ++){        if (!is_prime[i]){            prime[++ tot] = i;            for (int j = i << 1; j <= n; j += i)                 is_prime[j] = false;        }    }}

参考资料:OI Wiki

最新资讯