10

Elements of Programming Interviews を勉強していて、問題に行き詰まっています。与えられた n に対して、1 から n までのすべての素数を見つけるための C++ 関数を作成することについてです。

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;
    // is_prime[i] represents (2i+3) is prime or not

    vector<int> primes; // stores the primes from 1 to n

    primes.push_back(2);
    vector<bool> is_prime(size, true);

    for(long i = 0; i < size; ++i) {
       if(is_prime[i]) {
           int p = (i << 1) + 3;
           primes.push_back(p);
           // sieving from p^2, whose index is 2i^2 + 6i + 3
           for (long j = ((i * i) << 1) + 6 * i + 3; j < size; j += p) {
               is_prime[j] = false;
           }
       }
    }
}

特に、コメントされている「2i^2 + 6i + 3 をインデックスとする p^2 からのふるい分け」の部分が理解できません。他の部分については、それらがどのように機能するかについて大まかなアイデアをつかむことができますが、この '2i^2 + 6i + 3' がどこから来て、何をするのか、それと関連する部分がどのように機能するのかはわかりません。コードが機能します。

誰かがこのコードをよりよく説明できますか? ありがとうございました。

+

私はこの出力を取得しています(+'cout's to understand it)

./a.out 100
size is: 49
for i = 0 is_prime[i] is 1
pushing back p of size 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 6
((i * i) << 1) + 6 * i + 3 for i of 0 is 9
((i * i) << 1) + 6 * i + 3 for i of 0 is 12
((i * i) << 1) + 6 * i + 3 for i of 0 is 15
((i * i) << 1) + 6 * i + 3 for i of 0 is 18
((i * i) << 1) + 6 * i + 3 for i of 0 is 21
((i * i) << 1) + 6 * i + 3 for i of 0 is 24
((i * i) << 1) + 6 * i + 3 for i of 0 is 27
((i * i) << 1) + 6 * i + 3 for i of 0 is 30
((i * i) << 1) + 6 * i + 3 for i of 0 is 33
((i * i) << 1) + 6 * i + 3 for i of 0 is 36
((i * i) << 1) + 6 * i + 3 for i of 0 is 39
((i * i) << 1) + 6 * i + 3 for i of 0 is 42
((i * i) << 1) + 6 * i + 3 for i of 0 is 45
((i * i) << 1) + 6 * i + 3 for i of 0 is 48
for i = 1 is_prime[i] is 1
pushing back p of size 5
((i * i) << 1) + 6 * i + 3 for i of 1 is 11
((i * i) << 1) + 6 * i + 3 for i of 1 is 16
((i * i) << 1) + 6 * i + 3 for i of 1 is 21
((i * i) << 1) + 6 * i + 3 for i of 1 is 26
((i * i) << 1) + 6 * i + 3 for i of 1 is 31
((i * i) << 1) + 6 * i + 3 for i of 1 is 36
((i * i) << 1) + 6 * i + 3 for i of 1 is 41
((i * i) << 1) + 6 * i + 3 for i of 1 is 46
for i = 2 is_prime[i] is 1
pushing back p of size 7
((i * i) << 1) + 6 * i + 3 for i of 2 is 23
((i * i) << 1) + 6 * i + 3 for i of 2 is 30
((i * i) << 1) + 6 * i + 3 for i of 2 is 37
((i * i) << 1) + 6 * i + 3 for i of 2 is 44
for i = 3 is_prime[i] is 0
for i = 4 is_prime[i] is 1
pushing back p of size 11
for i = 5 is_prime[i] is 1
pushing back p of size 13
for i = 6 is_prime[i] is 0
for i = 7 is_prime[i] is 1
pushing back p of size 17
for i = 8 is_prime[i] is 1
pushing back p of size 19
for i = 9 is_prime[i] is 0
for i = 10 is_prime[i] is 1
pushing back p of size 23
for i = 11 is_prime[i] is 0
for i = 12 is_prime[i] is 0
for i = 13 is_prime[i] is 1
pushing back p of size 29
for i = 14 is_prime[i] is 1
pushing back p of size 31
for i = 15 is_prime[i] is 0
for i = 16 is_prime[i] is 0
for i = 17 is_prime[i] is 1
pushing back p of size 37
for i = 18 is_prime[i] is 0
for i = 19 is_prime[i] is 1
pushing back p of size 41
for i = 20 is_prime[i] is 1
pushing back p of size 43
for i = 21 is_prime[i] is 0
for i = 22 is_prime[i] is 1
pushing back p of size 47
for i = 23 is_prime[i] is 0
for i = 24 is_prime[i] is 0
for i = 25 is_prime[i] is 1
pushing back p of size 53
for i = 26 is_prime[i] is 0
for i = 27 is_prime[i] is 0
for i = 28 is_prime[i] is 1
pushing back p of size 59
for i = 29 is_prime[i] is 1
pushing back p of size 61
for i = 30 is_prime[i] is 0
for i = 31 is_prime[i] is 0
for i = 32 is_prime[i] is 1
pushing back p of size 67
for i = 33 is_prime[i] is 0
for i = 34 is_prime[i] is 1
pushing back p of size 71
for i = 35 is_prime[i] is 1
pushing back p of size 73
for i = 36 is_prime[i] is 0
for i = 37 is_prime[i] is 0
for i = 38 is_prime[i] is 1
pushing back p of size 79
for i = 39 is_prime[i] is 0
for i = 40 is_prime[i] is 1
pushing back p of size 83
for i = 41 is_prime[i] is 0
for i = 42 is_prime[i] is 0
for i = 43 is_prime[i] is 1
pushing back p of size 89
for i = 44 is_prime[i] is 0
for i = 45 is_prime[i] is 0
for i = 46 is_prime[i] is 0
for i = 47 is_prime[i] is 1
pushing back p of size 97
for i = 48 is_prime[i] is 0

これも私には意味がありません。

たとえば、なぜ p=5 の場合、以下の行で 5^2 = 25 ではなく 11 から削除し始めるのでしょうか? サイズ 5 の p を押し戻す ((i * i) << 1) + 6 * i + 3 for i of 1 is 11

また、11は素数ではありませんか？本当に混乱します。私を助けてください。ありがとうございました。

4

4 に答える 4

20

アルゴリズム

素数生成コードで使用されるアルゴリズムは、「エラトステネスのふるい」と呼ばれます。一般に、数値のリストを作成し、リストを反復処理します。現在の数値のすべての乗算がリストから削除され、残りの数値が素数になります。

たとえば、 を考えてみましょう[2,3,4,5,6,7,8,9,10,11,12,13,14,15]。2 に遭遇したので、リストからすべての偶数を削除します。

[2,3,5,7,9,11,13,15]

3も同じ：

[2,3,5,7,11,13]

5、7、11および13リストに乗算がないため、何も削除せず、素数のリストが残ります。

視覚的な例

ここに画像の説明を入力

この例 (ウィキペディアの厚意による) では、2、3、および 5 のすべての乗算がリストから削除されました。次に 7 が繰り返されるため、強調表示されます。暗い色の数字は素数、明るい色の数字は素数ではなく、灰色の数字はまだ正味に達していません。

コードの最適化

@BenJackson が述べたように、コードは 2 回最適化されます。

  • まず、偶数は素数ではないことがわかっているため (2 を除く)、3 から始まる奇数のみが格納されます。
  • 第二に、数 p については、p² からふるい始めるだけです。の乗算がふるいにかけられたときに、 if n<pthenはすでにふるいにかけられているため、これは正しいです。n*pn

これが不可解なコメントの理由です。

// sieving from p^2, whose index is 2i^2 + 6i + 3

アルゴリズムがベクトルの 2 番目の項目に到達したとしますi=2。インデックスiは数値を表すため、問題の数値は 5 です2i+3(最初の最適化)。

これ以降のすべての乗算5をふるいにかける必要があります。25を表すインデックス25は11です25=2*11+3。プリントアウトに続いて11, 16, 21, 26, ...、数値に対応する index25, 35, 45, 55, ..を削除します。削除したい 5 の奇数の乗算はすべて削除します。

詳細についてはWikipediaまたはWolfram MathWorldを参照してください。JavaScriptの優れたオンライン デモンストレーションがここにあります。

于 2013-06-03T04:43:06.503 に答える
8

素数の表には、3 から始まる奇数の値のみが格納されます (明らかに、偶数の値は素数にはなりません)。関係はint p = (i << 1) + 3、 またはの行で与えられp = 2i + 3ます。これを について解いてi、 を得るi = (p - 3)/2。iに対応するものは何p^2ですか？その 2 番目の式にプラグインし(2i+3)^2て単純化します。これで、 iforp^2に関して for がiできましたp。

例: としましょうi=1。したがって、エントリis_prime[i]は素数p=2i+3、またはのテストですp=5。そうです、それはプライムです。これで、seive (他の場所で説明されています) は 25 で非素数のマークを付け始めたいと考えています。25 にi対応するものを知る必要p*pがi=(p-3)/2ありますj=11。コードは、(上で示したように) 中間ステップをスキップして計算し、直接j=2i^2+6i+3取得しています。j=11

于 2013-06-03T04:34:01.793 に答える
1

次のような行:

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;

...

for(long i = 0; i < size; ++i) {
   if(is_prime[i]) {
       int p = (i << 1) + 3;

対応する可能な素数3、5、7、9などに0、1、2、3を繰り返してi使用することにより、潜在的な素数3、5、7などを繰り返すことができるようにするための「ハック」です。p

それ以外は基本的なプライムシーブです。

于 2013-06-03T04:34:41.790 に答える