素数のふるい方

素数のふるい方
本稿では、素数を判定する際に用いられる二つの選別方法をまとめて紹介します。Ethat thenes篩法（Sieve of Eators thenes）とEular篩法（Sieve of Euler）。

ブログリンク：http://haoyuanliu.github.io/2016/04/12/sieve/

ペアです。訪問量を騙しに来ました。O(∩∩)O~

Entosthenes篩法
基本思想:
素数の倍数はきっと素数ではない
実現方法

は、長さNの配列を用いてデジタル素数情報（0は素数、1は非素数を示す）を保持する

。

は、まず、配列を0に初期化する。すなわち、すべての数は素数

であると考える。

は、最初の素数2から始まり、すべての2の倍数を素数として記憶し（もうすぐ配列対応値を1とする）、Nを超える範囲まで；

は、その後3を巡回し、同じ動作を実行する。

が4に実行されたとき、以前にその値を1に設定したので、すなわち非素数と判定された場合、++は次の素数5を動作させる。

は、最後にすべての素数が得られるまで、上述の動作を順次行う。

例としての操作（N=20）
i
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
5
1
1
1
7
1
ALL
0
0
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
1
0:素数1:非素数
コードの実装

#include <iostream>
using namespace std;
int main()
{
    int num;
    cin >> num;
    int flag[1000] = {0};
    int prime[1000];
    int count = 0;
    for(int i = 2; i < num; ++i)
    {
        if(!flag[i])
            prime[count++] = i;
        for(int j = i + i; j <= num; j += i)
            flag[j] = 1;
    }
    cout << "The number is: " << count << endl;
}

このアルゴリズムの時間複雑度はO（nloglogn）であり、空間複雑度はO（n）である。上からも分かるように、このアルゴリズムは6のように素数が2の時に一回処理したことがあります。3の時にも1回処理しました。同じ操作を繰り返しました。次は改善アルゴリズムを紹介します。
エulerふるい
核心的な考え
各合数は最小の素因数だけで選別するように規定されています。例えば、6は2と3の因数があり、2だけで選別と配置操作を行います。3の場合は条件によってスキップします。
例としての操作（N=20）
i
j
p[j]
count
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
2
1
1
3
0
2
2
1
3
1
3
2
1
4
0
2
2
1
5
0
2
3
1
5
1
3
3
1
6
0
2
3
1
7
0
2
4
1
8
0
2
4
1
9
0
2
4
1
10
0
2
4
1
ALL
0
0
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
1
0:素数1:非素数
コード
下に直接コードを入れます。

#include <iostream>
using namespace std;
#define Length 1000000
int main()
{
    int num;
    cin >> num;
    int flag[Length] = {0};
    int prime[1000];
    int count = 0;
    for(int i = 2; i <= num; ++i)
    {
        if(!flag[i])
        {
            prime[++count] = i;
        }
        for(int j = 1; j <= count; ++j)
        {
            if(i * prime[j] > num)
                break;
            flag[i * prime[j]] = 1;
            if(i % prime[j] == 0)
                break;
        }
    }
    cout << count << endl;
}

コード解析
コアコードif(i % prime[j] == 0) break；

は、各合計がビット

に配置されることを保証する。

各合数は一回だけ選別され、その最小係数を取る場合

Eularアルゴリズムの時間複雑度はO（n）であり，Eatorsthenesアルゴリズムに比べて大きく向上した。
Github:https://github.com/haoyuanliu 個人ブログ：http://haoyuanliu.github.io/
個人のウェブサイト、訪問を歓迎して、評論を歓迎します！