この情報は東賓納実戦アルゴリズム講座に基づいて整理されている.他の素数判別アルゴリズムとテストステロン体を比較し,テストステロン体をいつ使用すべきかを説明する.

エラトステネスのふるい?

アラトネスのふるいは最も代表的な少数の判別アルゴリズムである.このアルゴリズムは大量の素数を迅速かつ正確に求めるために用いられる.では,エラトネスの体を学ぶ前に,少数を判別するアルゴリズムを制定した.

素数判別アルゴリズム

1.判別する数を：O（N）で割る

function isPrimeNumber(n) {
    for (let i = 2; i < n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

isPrimeNumber(97) // true

上記アルゴリズムは2から判別すべき数まで,すべての数を遍歴することにより小数であるか否かを判断する.このアルゴリズムの時間的複雑度はO(N)である.このアルゴリズムは判別すべき数の平方根を決定できるので,O(n^(1/2))で容易に計算できる.

2.判別する数を平方根で割る:O(N^(1/2))

function isPrimeNumber(n) {
    for (let i = 2; i**2 < n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

isPrimeNumber(97)

上記アルゴリズムは,判別すべき数の平方根に回転することによって素数であるか否かを判断する.原理は,すべての約数が中間の約数(平方根)に準じ,乗算に対して対称である.例えば、80の約数は以下の通りである.

例：80の少数の判別

80の約数は1, 2, 4, 5, 8, 10, 16, 20, 40, 80です.このとき8 x 10 = 10 x 8は対称である.

√80は約8です.xxxx,80の薬水中間価格.

したがって,特定の自然数のすべての薬水を探すには,平方根を確認するだけでよい.
たとえば、80を8で割ると10になります.

...少数のエラ氏体を判別するために用いられる。

しかし,上記のアルゴリズムのように,1,2個の小数を判別するのではなく,一度に大量の小数を判別するならば,エラトネスのふるいは有効である.
エラトネスのふるいはまず配列を割り当て,小数を判別する範囲に指定し,対応する値をインデックスに入れる.
例えば、1から25まで判別するとする.

エラトスタイニスチェエシ

1から25までの数字の中で、少数の人の数字がどれらがあるかを判別します.

2 D配列を生成し、値を初期化します.

2から、特定の数字の倍数に対応するすべての数字を削除します.

まず2の倍数をクリアします(自身をクリアしません).

3の倍数を消去しましょう(自分を消去しません).

消去された数値をスキップします.

4はクリアされ、スキップされました.これらの手順を繰り返します.

2から残りの数字を出力します.

出力:23 7 11 13 19 23
これらのプロセスをJSソースコードに移行しましょう.

function primeNumberSieve(n) {
    const arr = new Array(n+1);
    // 인덱스에 해당하는 값 채우기
  	for (let i = 2; i <= n; i++) {
        arr[i] = i;
    }
  	 // 약수 여부 확인하기
    for (let i = 2; i <= n; i++) {
        if (arr[i] === 0) continue;
        for (let j = i * 2; j <= n; j += i) {
            arr[j] = 0;
        }
    }
    
  	// 소수인 값 넣어주기
    const prime = [];
    for (let i = 2; i <= n; i++) {
        if (arr[i] !== 0) prime.push(arr[i])
    }
    return prime;
}

primeNumberSieve(25); // [2, 3, 5, 7, 11, 13, 17, 19, 23]

エラトネスの体は時間複雑度O(nlog(logn))の最も速く,最も正確な求素数アルゴリズムである.