素数筛的介绍

前言

素数是一个正整数,只能除以 1 和自身,不包括 1。几个世纪以来,这种类型的数字因其在各种数学概念(包括密码学和数论)中的独特性质和重要性而使数学家着迷。此外,素数在数学之外还有实际应用,例如在计算算法和数据编码中。然而,识别素数可能是一项具有挑战性的任务,特别是对于大数,并且正在研究寻找有效的素数生成和测试方法。尽管困难重重,素数仍然是数学的一个迷人而基本的方面,还有许多迷人的性质有待发现。

为了判断一个数是否为素数,除了使用这个定义法,还有更多复杂度较小的算法,这些算法也被称作素数筛,该文即是来介绍不同素数筛算法的。

定义法

优化前

因为素数是只能被自身与1整除的数字,那么我们就可以判断这个数字能否被比它小的数字整除,这是一个十分简单粗暴的方法,如果要列出前n个正整数中的素数,时间复杂度达到了惊人的O(n²)

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int num) {
    if (num == 2) return true;
    for (int i = 2; i < num; i++) {
        if (num % i == 0)return false;
    }
    return true;
}

void outPrime(int arrange) {
    for (int i = 2; i <= arrange; i++) {
        if (isPrime(i)) cout << i << endl;
    }
}

int main() {
    outPrime(100);
}

这一段代码可以输出前1~100之间的素数,但是一旦这个范围达到1~1000000就会导致要等待很长一段时间才能出结果,因为他的复杂度是O(n²)。

优化后

在判断n是否为素数时,实际上我们不必让n取模循环到n-1,根据已知数学知识,我们可以只用循环到sqrt(n)即可,于是整段代码的时间复杂度变为O(nlogn)

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int num) {
    if (num == 2) return true;
    for (int i = 2; i * i < num; i++) {
        if (num % i == 0)return false;
    }
    return true;
}

void outPrime(int arrange) {
    int temp = 0;
    for (int i = 2; i <= arrange; i++) {
        if (isPrime(i)) cout << i << endl; 
    }
}

int main() {
    outPrime(1000000);
}

这串代码耗时就比优化前要快很多,当然,为了更快的得到素数表,仍然有时间复杂度更小的算法,下面我们来介绍素数筛。

素数筛

埃氏筛

举个例子,我们先列出2~16(1不是素数):

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

然后从2开始,将所选数字的所有倍数标红

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

接着下一个素数是3

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

下一个素数是5,但是5 * 5 > 16,超出了这一串数字的上限,所以不需要继续往后面处理了。

于是颜色仍然是黑色的就是素数。

#define MAXN 1000
#include <bits/stdc++.h>

using namespace std;

int main() {
    int isPrime[1001] = {0}; // 若为素数则是1
    memset(isPrime, 1, sizeof(isPrime));
    for (int i = 2; i * i <= MAXN; i++) {
        if (isPrime[i]) {
            for (int j = 2; i * j <= MAXN; j++) {
                isPrime[i * j] = 0; // 为倍数则不是素数
            }
        }
    }
    for (int i = 2; i <= MAXN; i++) {
        if (isPrime[i]) {
            cout << i << endl;
        }
    }
}

代码实现过程如上,可以输出1~1000以内的素数,其复杂度是O(n)=nloglogn。

但是我们能注意到,一个数可以是不同素数的倍数,比如说15 = 3 * 5,那么循环到3和5的时候都会对15进行一次筛选操作,于是会进行一次重复无效操作,那么我们引入了欧拉筛这一算法,这个算法的本质是让合数被它的最小质因数筛选掉

欧拉筛

再次引入1~16

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Primes = [2]

让2与Primes里的元素求积,2*2=4,所以将4标红

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Primes = [2,3]

让3与Primes里的元素求积,3*2 = 6,3*3 = 9,所以将6和9标红

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Primes = [2,3]

让4与Primes里的元素求积,4*2 = 8,4*3 = 12,将8和12标红

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Primes = [2,3,5]

以此类推,10、15、25标红,因为25>16,所以跳过

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Primes = [2,3,5]

最后循环到8就可以将所有合数筛掉

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

因为任意合数都能拆成一个素数乘一个整数,所以我们只需要找出这个最小的素数即可。

#include <bits/stdc++.h>
#define MAXN 100000000

using namespace std;
int isPrime[100000000];

int main() {
    vector<int> primes;
    memset(isPrime, 1, sizeof(isPrime)); // 质数为1,筛掉合数为0
    for (int i = 2; i <= MAXN; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int j : primes) {
            if (i * j > MAXN)break;
            isPrime[i * j] = 0;
        }
    }
    for (int num : primes) {
        cout << num << endl;
    }
}

该代码的时间复杂度只有O(n)=n,如果把底下的输出语句删掉,该代码获得1~1e之间的素数只要2~3s,巨快!

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇