素?cái)?shù)的計(jì)算: 從試除到篩法(C++實(shí)現(xiàn))

什么是素?cái)?shù)

素?cái)?shù)又稱質(zhì)數(shù)，是指大于1的自然數(shù)中浦妄，除了1和它本身，不能被其它自然數(shù)整除的數(shù)字见芹。1被定義為非素?cái)?shù)剂娄。大于1的自然數(shù)，如果不是素?cái)?shù)則為合數(shù)玄呛。上古大神歐幾里得已經(jīng)證明了有無窮多個(gè)素?cái)?shù)存在（歐幾里得定理）阅懦。

素?cái)?shù)定理

引入維基百科的描述

在數(shù)論中，素?cái)?shù)定理描述素?cái)?shù)在自然數(shù)中分布的漸進(jìn)情況徘铝，給出隨著數(shù)字的增大耳胎，素?cái)?shù)的密度逐漸降低的直覺的形式化描述

素?cái)?shù)的個(gè)數(shù)是有規(guī)律可循的惯吕，對(duì)于正實(shí)數(shù)x，定義 $\pi (x)$ 為素?cái)?shù)計(jì)數(shù)函數(shù)怕午，即不大于x的素?cái)?shù)的個(gè)數(shù)混埠。
$\pi(x)$ 的估計(jì)方法有很多，這里介紹比較簡(jiǎn)單的一種:
$\pi(x) \approx \frac{x}{\ln x}$
其中 $\ln x$ 是x的自然對(duì)數(shù)诗轻。
維基百科中給出了 $x$ 從10到 $10^{25}$ 钳宪， $\pi(x)$ 與 $\frac{x}{\ln x}$ 的數(shù)值，可以看出隨著 $x$ 的增長(zhǎng)扳炬， $\frac{\pi(x)}{\frac{x}{\ln x}}$ 始終小于 $1.17$ （這里的比值很關(guān)鍵吏颖，我們后面需要用來估計(jì)用于存儲(chǔ)素?cái)?shù)的數(shù)組的預(yù)分配空間的大小）恨樟。

常規(guī)計(jì)算方法（試除法）及實(shí)現(xiàn)

基本思想

根據(jù)定義半醉，給定一個(gè)自然數(shù)，先判斷它是否是素?cái)?shù)劝术。若要計(jì)算出所有不大于n的素?cái)?shù)缩多，則從2到n，依次判斷是否是素?cái)?shù)养晋。根據(jù)如何判斷一個(gè)數(shù)是否是素?cái)?shù)又有以下幾種常規(guī)方法衬吆。

常規(guī)方法一

為了判斷自然數(shù)x是否是素?cái)?shù)，我們可以從2開始绳泉，分別除以不大于x的每個(gè)數(shù)逊抡，如果存在能整除x的數(shù)，則x不是素?cái)?shù)零酪。
常規(guī)方法一的c++實(shí)現(xiàn)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 判斷n是否為素?cái)?shù)
bool is_prime(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

// 計(jì)算所有不大于n的素?cái)?shù)
void get_prime(vector<int>& prime, int n)
{
    for(int i = 2; i <= n; ++i)
        if(is_prime(i)) // 判斷i是否是素?cái)?shù)
            prime.push_back(i);
}
int main()
{
    int n = 100000;
    vector<int> prime;
    get_prime(prime, n);
    return 0;
}

該算法的時(shí)間復(fù)雜度為
$O(\sum_{i=2}^{n}i^2) =O(n^2)$
實(shí)際上我們沒必要比較這么多次冒嫡，下面我們介紹方法二。

常規(guī)方法二

如果 $n$ 為合數(shù)四苇，已知 $n=\sqrt{n} \times \sqrt{n}$ 孝凌，假設(shè) $n=xy$ ，如果 $x>\sqrt{n}$ 月腋，那么 $y$ 必然小于 $\sqrt{n}$ 蟀架。即我們只需要判斷到 $\sqrt{n}$ 即可。
常規(guī)方法二的C++實(shí)現(xiàn)
實(shí)際上只需要根據(jù)方法一更改is_prime函數(shù)即可罗售，其余代碼完全一樣辜窑。
is_prime函數(shù)

bool is_prime(int n)
{
    if (n < 2)
        return false;
    /**
     * 只需要判斷到根號(hào)n即可，這里必須要使用小于等于符號(hào)
     * （不能僅僅使用小于符號(hào)寨躁，例如判斷9）
     **/
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

該算法的時(shí)間復(fù)雜度為
$O(\sum_{i=2}^{n}\sqrt{i}) = O(n\sqrt{n})$
實(shí)際上我們的算法還有進(jìn)步的空間穆碎，下面介紹常用的兩種性能不錯(cuò)的篩法。

埃拉托斯特尼篩法及C++實(shí)現(xiàn)

基本思想

埃拉托斯特尼篩法（sieve of Eratosthenes ） 是古希臘數(shù)學(xué)家埃拉托斯特尼發(fā)明的計(jì)算素?cái)?shù)的方法职恳。對(duì)于求解不大于 $n$ 的所有素?cái)?shù)所禀，我們先找出 $\sqrt{n}$ 內(nèi)的所有素?cái)?shù) $p_1,p_2,...,p_{k-1}, p_k$ 方面，其中 $k = \lfloor \sqrt{n}\rfloor$ ，依次剔除 $p_i(1 <= i <=k)$ 的倍數(shù)色徘，剩下的所有數(shù)都是素?cái)?shù)恭金。
維基百科中有一張關(guān)于使用埃拉托斯特尼篩法求解素?cái)?shù)的GIF圖

埃拉托斯特尼篩法求解素?cái)?shù)

下面我們來看一個(gè)來自維基百科的例子，如果求25內(nèi)的所有素?cái)?shù)
1.列出大于等于2小于等于25的所有數(shù)組成的序列：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

去掉素?cái)?shù)2的所有倍數(shù)：

2 3 5 7 9 11 13 15 17 19 21 23 25

去掉素?cái)?shù)3的所有倍數(shù)：

2 3 5 7 11 13 17 19 23 25

去掉素?cái)?shù)5的所有倍數(shù)：

2 3 7 11 17 19 23

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=5%20%3D%20%5Csqrt%7B25%7D" alt="5 = \sqrt{25}" mathimg="1">褂策，所以算法結(jié)束横腿。剩下的所有數(shù)都是素?cái)?shù)。

埃拉托斯特尼篩法的證明

證明之前我們先粗略介紹算術(shù)基本定理斤寂。算法基本定理的描述是：每個(gè)大于1的自然數(shù)均可寫為素?cái)?shù)的積耿焊，而且這些素因子按大小排列之后，寫法僅有一種方式遍搞。然后開始我們的證明（反證法）：
假設(shè)正整數(shù) $n$ 為通過埃拉托斯特尼篩法得到序列中的合數(shù)且 $n$ 不能被小于等于 $\sqrt{n}$ 的素?cái)?shù)整除罗侯。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=n" alt="n" mathimg="1">是合數(shù)，則必然有 $xy=n$ 溪猿，如果 $1<x<\sqrt{n}$ 钩杰，那么 $\sqrt{n} < y < n$ ，又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=n" alt="n" mathimg="1">不能被小于等于 $\sqrt{n}$ 的素?cái)?shù)整除诊县，故 $x$ 為合數(shù)讲弄，根據(jù)算術(shù)基本定理,合數(shù) $x$ 一定寫成關(guān)于某個(gè)素?cái)?shù) $p$ 的積，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=1%20%3C%20x%20%3C%20%5Csqrt%7Bn%7D" alt="1 < x < \sqrt{n}" mathimg="1">翎冲，則 $1<p<\sqrt{n}$ 垂睬。與假設(shè)矛盾，證畢抗悍。

C++實(shí)現(xiàn)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void get_prime(vector<int> &prime, int n)
{
    // 初始化一個(gè)布爾數(shù)組，用于判斷下標(biāo)i是否是素?cái)?shù)
    vector<bool> is_prime(n + 1, true);
    if (n < 2)
        return;
    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i])
        {
            prime.push_back(i); // 把素?cái)?shù)加入到數(shù)組中
            // 這里只需要從 i * i 開始篩選即可钳枕，證明見下文
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}
int main()
{
    int n = 100;
    vector<int> prime;
    get_prime(prime, n);
    // 打印計(jì)算出的素?cái)?shù)
    for_each(prime.begin(), prime.end(), [](int &n) {
        cout << n << " ";
    });
    return 0;
}

在上述代碼的get_prime函數(shù)中

for (int j = i * i; j <= n; j += i)

這一行中的的 $j$ 是從 $i^2$ 開始的缴渊，也就是說對(duì)于當(dāng)前素?cái)?shù) $i$ 是從 $i^2$ 開始篩選的，且剩余序列中從 $2$ 到 $i^2-1$ 的所有數(shù)都是素?cái)?shù)鱼炒。證明如下：
如果 $i=2$ 衔沼， $i^2$ 之前的序列為: $2,3$ ，都是素?cái)?shù)昔瞧。
如果 $i>2$ 指蚁，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=1%3Ci%5E2-1%20%3C%20i%5E2" alt="1<i^2-1 < i^2" mathimg="1">，所以 $i-1<\sqrt{i^2-1} < i$ 自晰， $i-1$ 為 $i$ 的前一個(gè)數(shù)凝化，即 $\sqrt{i^2-1}$ 大于 $i-1$ 及之前的所有數(shù)。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=i" alt="i" mathimg="1">之前的所有素?cái)?shù)都篩選過了酬荞，且均小于 $\sqrt{i^2-1}$ 搓劫，根據(jù)埃拉托斯特尼篩法可知瞧哟，序列中 $i^2$ 之前的所有數(shù)都是素?cái)?shù)，所以 $i$ 只需要從 $i^2$ 開始篩選即可枪向，證畢勤揩。
埃拉托斯特尼篩法的時(shí)間復(fù)雜度為 $O(n\log \log n)$ ，證明俺暫時(shí)不會(huì)（╯－＿－）╯╧╧

歐拉篩法及C++實(shí)現(xiàn)

基本思想

回顧上文的埃拉托斯特尼篩法秘蛔，核心思想就是依次剔除素?cái)?shù)的倍數(shù)陨亡。這里我們很容易就能想到此算法存在的缺點(diǎn)：對(duì)于兩個(gè)素?cái)?shù)的公倍數(shù)，我們可能會(huì)進(jìn)行多次剔除深员。
于是便出現(xiàn)了歐拉篩法负蠕，核心思想便是對(duì)于一個(gè)沒被篩選過的數(shù)來說，它只需要被第一個(gè)整除它的素?cái)?shù)篩掉就行辨液。直接上代碼虐急。

C++實(shí)現(xiàn)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void get_prime(vector<int> &prime, int n)
{
    if (n < 2)
        return;
    // 初始化一個(gè)布爾數(shù)組，用于記錄每個(gè)數(shù)是否是素?cái)?shù)
    vector<bool> is_prime(n + 1, true);
    for (int i = 2; i <= n; ++i)
    {
        // 如果是素?cái)?shù)則將該數(shù)字加入到素?cái)?shù)序列中
        if (is_prime[i])
            prime.push_back(i);
        // 從第一個(gè)素?cái)?shù)開始滔迈，將它的倍數(shù)設(shè)置為非素?cái)?shù)
        for (int j = 0; j < prime.size() && i * prime[j] <= n; ++j)
        {
            is_prime[i * prime[j]] = false;
            /**
             * 如果 i%prime[j] == 0, 則 i = prime[j] * a
             * i * prime[j+1] = prime[j] * a * prime[j+1]
             * prime[j]已經(jīng)篩過i * prime[j+1]這個(gè)數(shù)了止吁，不需要用prime[j+1]再篩選一次
             **/
            if (i % prime[j] == 0)
                break;
        }
    }
}

int main()
{

    int n = 100;
    vector<int> prime;
    get_prime(prime, n);
    for_each(prime.begin(), prime.end(), [](int &n){
        cout << n << " ";
    });
    return 0;
}

在上述代碼的get_prime函數(shù)中

    if (i % prime[j] == 0)
        break;

這里就是歐拉篩法的核心所在啦，對(duì)于數(shù)字 $i$ 來說燎悍，如果 $prime[j]$ 能整除 $i$ 敬惦，則說明 $i=prime[j] \times a$ ，其中谈山， $1<a<i$ 俄删，而對(duì)于比 $prime[j]$ 大的素?cái)?shù) $prime[j+1]$ ， $i \times prime[j+1] = prime[j] \times a \times prime[j+1]$ 奏路，也就是說 $i \times prime[j+1]$ 已經(jīng)被 $prime[j]$ 篩選過了畴椰，不需要再篩選了。
歐拉篩法的時(shí)間復(fù)雜度為 $O(n)$ 鸽粉，證明俺暫時(shí)也不會(huì)（╯－＿－）╯╧╧

總結(jié)

本文一共介紹了四種計(jì)算素?cái)?shù)的方法斜脂。兩種試除法，試除法一時(shí)間復(fù)雜度為 $O(n^2)$ 触机，試除法二時(shí)間復(fù)雜度為 $O(n \sqrt{n})$ 帚戳，兩者的空間復(fù)雜度為 $O(1)$ ；兩種篩法儡首，埃拉托斯特尼篩法時(shí)間復(fù)雜度為 $O(n\log \log n)$ 片任，歐拉篩法時(shí)間復(fù)雜度為 $O(n)$ ，兩者空間復(fù)雜度均為 $O(n)$ 蔬胯。
在我們上面的實(shí)現(xiàn)中還存在一個(gè)問題值得我們思考对供，那就是如何存儲(chǔ)素?cái)?shù)，上面的代碼中我們是用C++的vector存儲(chǔ)素?cái)?shù)笔宿，vector雖為動(dòng)態(tài)數(shù)組犁钟，能夠動(dòng)態(tài)添加和刪除數(shù)據(jù)棱诱，但是在大部分STL的vector的實(shí)現(xiàn)版本中，vector都是有預(yù)分配空間的涝动，當(dāng)預(yù)分配的空間的容量不夠時(shí)迈勋，便會(huì)重新分配更大的空間，并把所有的舊數(shù)據(jù)復(fù)制到新的空間中醋粟，所以這里的開銷也是難以忽視的（其它語言也存在類似的問題）靡菇。所以，我們需要知道我們應(yīng)該分配多少的空間來存儲(chǔ)求得的素?cái)?shù)米愿，也就是說我們得估計(jì)素?cái)?shù)的個(gè)數(shù)以便預(yù)分配存儲(chǔ)空間厦凤。
而如何估計(jì)素?cái)?shù)的數(shù)量？前面我們介紹的素?cái)?shù)定理就排上用場(chǎng)啦育苟，這里就不具體說啦较鼓。

參考資料

質(zhì)素 - 維基百科，自由的百科全書
算術(shù)基本定理 - 維基百科违柏，自由的百科全書
素?cái)?shù)計(jì)數(shù)函數(shù) - 維基百科博烂，自由的百科全書
Sieve of Eratosthenes - Wikipedia, the free encyclopedia

本作品采用知識(shí)共享署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際許可協(xié)議進(jìn)行許可。轉(zhuǎn)載請(qǐng)注明: 作者staneyffer漱竖，首發(fā)于我的博客禽篱，原文鏈接: https://chengfy.com/post/10

最后編輯于：2018.11.16 00:26:02

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市馍惹，隨后出現(xiàn)的幾起案子躺率，更是在濱河造成了極大的恐慌，老刑警劉巖万矾，帶你破解...
沈念sama閱讀 216,372評(píng)論 6贊 498
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件悼吱，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡良狈，警方通過查閱死者的電腦和手機(jī)舆绎，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,368評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來们颜，“玉大人，你說我怎么就攤上這事猎醇】唬” “怎么了？”我有些...
開封第一講書人閱讀 162,415評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵硫嘶，是天一觀的道長(zhǎng)阻问。經(jīng)常有香客問我，道長(zhǎng)沦疾，這世上最難降的妖魔是什么丽啡？我笑而不...
開封第一講書人閱讀 58,157評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任惦费，我火速辦了婚禮励稳，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘凳谦。我一直安慰自己，他們只是感情好衡未，可當(dāng)我...
茶點(diǎn)故事閱讀 67,171評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布尸执。她就那樣靜靜地躺著，像睡著了一般缓醋。火紅的嫁衣襯著肌膚如雪如失。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,125評(píng)論 1贊 297
城市分裂傳說
那天送粱，我揣著相機(jī)與錄音褪贵，去河邊找鬼。笑死抗俄，一個(gè)胖子當(dāng)著我的面吹牛脆丁，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播橄镜，決...
沈念sama閱讀 40,028評(píng)論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼偎快，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了洽胶？” 一聲冷哼從身側(cè)響起晒夹，我...
開封第一講書人閱讀 38,887評(píng)論 0贊 274
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎姊氓，沒想到半個(gè)月后丐怯，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,310評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡翔横，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,533評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年读跷，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片禾唁。...
茶點(diǎn)故事閱讀 39,690評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡效览，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出荡短，到底是詐尸還是另有隱情丐枉，我是刑警寧澤，帶...
沈念sama閱讀 35,411評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布掘托，位于F島的核電站瘦锹，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜弯院，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,004評(píng)論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一辱士、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧听绳，春花似錦颂碘、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,659評(píng)論 0贊 22
一樁弒父案凭涂，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至贴妻，卻和暖如春切油，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背名惩。一陣腳步聲響...
開封第一講書人閱讀 32,812評(píng)論 1贊 268
情欲美人皮
我被黑心中介騙來泰國(guó)打工澎胡，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人娩鹉。一個(gè)月前我還...
沈念sama閱讀 47,693評(píng)論 2贊 368
代替公主和親
正文我出身青樓攻谁，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親弯予。傳聞我的和親對(duì)象是個(gè)殘疾皇子戚宦，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,577評(píng)論 2贊 353

素?cái)?shù)的計(jì)算: 從試除到篩法(C++實(shí)現(xiàn))

什么是素?cái)?shù)

素?cái)?shù)定理

常規(guī)計(jì)算方法（試除法）及實(shí)現(xiàn)

基本思想

常規(guī)方法一

常規(guī)方法二

埃拉托斯特尼篩法及C++實(shí)現(xiàn)

基本思想

埃拉托斯特尼篩法的證明

C++實(shí)現(xiàn)

歐拉篩法及C++實(shí)現(xiàn)

基本思想

C++實(shí)現(xiàn)

總結(jié)

參考資料

推薦閱讀更多精彩內(nèi)容