Habréについては、すでに何度もそれについて書いています。 しかし、ほとんどの場合、それは数Nまでのすべての素数を見つけることでした。 N個の最初の素数を見つける問題をどのように解決したかについてお話します。
一見すると、これらのタスクに実質的な違いはないように思えるかもしれません。 そして、除数の列挙が非常に悪い仕事をすることを理解するまで、これは確かにそうです。
完了した作業の結果、100万個の素数を見つけるのに0.262秒しかかかりません。これはもちろん制限ではありませんが、すでに印象的です。 このアルゴリズムはC ++で実装されています。
素数に関する前回の記事の著者のように、私はこの問題を真正面から解決し始めました。 したがって、素数pは2つの除数-oneとpを持っているということです。 最初に頭に浮かぶのは、以前のすべての数字で割って各数字をチェックすることです。
アイデアは悪いことが判明しました。 プログラムの最初の30分後に、100万の単純なプログラムを探してこれを実現しました。 結果は次のとおりです。
10,000-2,349秒
100,000-293.552秒
1,000,000-待たなかった
前述の記事のように、アルゴリズムの最適化を設定しました。 第一に、2が唯一の素数の偶数であるため、偶数をチェックすることは意味がありません。 仕切りと同じ-あなたもものをチェックすることはできません。 第三に、除数として、チェックされた数の半分を超えない数を取るだけで十分です。 以下がその結果です。
// Listing 1 <br/>
<br/>
#include <iostream> <br/>
#include <vector> <br/>
#include <ctime> <br/>
<br/>
using namespace std ; <br/>
<br/>
int main ( ) <br/>
{ <br/>
clock_t start = clock ( ) ; <br/>
<br/>
const int AIM = 10000 ; <br/>
<br/>
vector < int > prime_nums ; <br/>
prime_nums. push_back ( 2 ) ; <br/>
<br/>
for ( int num = 3 ; prime_nums. size ( ) < AIM ; num + = 2 ) <br/>
{ <br/>
bool isprime = true ; <br/>
for ( int i = 3 ; i <= num / 2 ; i + = 2 ) <br/>
{ <br/>
if ( num % i == 0 ) <br/>
{ <br/>
isprime = false ; <br/>
break ; <br/>
} <br/>
} <br/>
<br/>
if ( isprime ) <br/>
prime_nums. push_back ( num ) ; <br/>
} <br/>
<br/>
cout << prime_nums [ AIM - 1 ] ; <br/>
<br/>
clock_t end = clock ( ) ; <br/>
cout << " \n ----------------" << endl ; <br/>
cout << "Time: " << double ( end - start ) / CLOCKS_PER_SEC << " sec" << endl ; <br/>
}
それは良くなりましたが、私はまだ百万を待つことができませんでした
10,000-0,589秒
100,000-72.662秒
1,000,000-20分後に待機を停止しました
このアルゴリズムを長時間最適化し続けることができることは明らかです。これが基本的に私がやったことです。 5と0で終わる番号をチェックすることはできません。最も一般的な除数のリストを作成し、それらの各番号を最初にチェックすることができます。 ある時点で、すでに見つかった素数でのみ新しい数をチェックすることで問題を解決できるように思えました。 重要な結果はもたらされませんでした。 問題は、新しい番号が追加されるたびにチェックの数が増え、除算操作が最も難しいことの1つであることでした。
私は検索に行きました。 エラトステネスのふるいについて学びました。 しかし、私は自分のタスクのためにアルゴリズムを使用することはできません。 事前に知られていない* N個の素数を見つけるためにふるいにかける必要がある数。 そのため、次のように、ニーズに合わせてアルゴリズムを変更することにしました。
自然数の大きなセットを事前にふるいにかけることは有益ではありません。 したがって、目的の結果が得られるまで、自然数のセットをふるいにかける必要があります。 さらに、すでに見つかった素数に対して、新しいセットをそれぞれふるいにかけなければなりません。 一連の最適化の後に得られるコードは次のとおりです。
// Listing 2 <br/>
<br/>
#include <iostream> <br/>
#include <ctime> <br/>
#include <vector> <br/>
<br/>
using namespace std ; <br/>
<br/>
int main ( ) <br/>
{ <br/>
clock_t start = clock ( ) ; <br/>
<br/>
const int AIM = 1000000 ; <br/>
<br/>
int startSize = AIM ; // <br/>
int addSize = AIM ; // <br/>
<br/>
vector < bool > nums ( startSize ) ; <br/>
vector < int > primeNums ( AIM ) ; <br/>
<br/>
int foundPrimes = 0 ; <br/>
<br/>
for ( int i = 2 ; i < startSize ; i ++ ) <br/>
nums [ i ] = true ; <br/>
<br/>
bool addition = false ; <br/>
int adder = 0 ; <br/>
while ( true ) <br/>
{ <br/>
if ( addition ) <br/>
{ <br/>
nums. resize ( nums. size ( ) + addSize, true ) ; <br/>
<br/>
// <br/>
for ( int i = 0 ; i < foundPrimes ; i ++ ) <br/>
{ <br/>
int cur_num = primeNums [ i ] ; <br/>
if ( ( addSize + ( ( nums. size ( ) - addSize ) % cur_num ) ) < cur_num ) <br/>
continue ; <br/>
for ( int j = ( ( nums. size ( ) - addSize ) / cur_num ) * cur_num ; j < nums. size ( ) ; j + = cur_num ) <br/>
nums [ j ] = false ; <br/>
} <br/>
} <br/>
else <br/>
addition = true ; <br/>
<br/>
<br/>
int iter ; <br/>
if ( foundPrimes == 0 ) <br/>
iter = 2 ; <br/>
else <br/>
iter = primeNums [ foundPrimes - 1 ] + 2 ; <br/>
<br/>
for ( ; iter < nums. size ( ) ; iter ++ ) <br/>
{ <br/>
// <br/>
if ( nums [ iter ] ) <br/>
{ <br/>
primeNums [ foundPrimes ] = iter ; <br/>
foundPrimes ++ ; <br/>
if ( foundPrimes == AIM ) <br/>
break ; <br/>
// <br/>
for ( int j = iter + iter ; j < nums. size ( ) ; j + = iter ) <br/>
nums [ j ] = false ; <br/>
} <br/>
else <br/>
continue ; <br/>
<br/>
} <br/>
if ( foundPrimes == AIM ) <br/>
break ; <br/>
} <br/>
<br/>
cout << "Last prime: " << primeNums [ AIM - 1 ] ; <br/>
<br/>
clock_t end = clock ( ) ; <br/>
cout << " \n ----------------" << endl ; <br/>
cout << "Time: " << double ( end - start ) / CLOCKS_PER_SEC << " sec" << endl ; <br/>
return 0 ; <br/>
}
結果はさらに少し驚きました。
10,000-0.001秒
100,000-0.021秒
1,000,000-0,262秒
...
10,000,000-2,999秒
これについて、1Mの最初の素数を見つけるというタスクで、私は結局は終わりました。 結果は完全に満足しました。 しかし、他に何ができますか？ エラトステネスのふるい、たとえばSundaramふるいに基づいて、既知のアルゴリズムを実装できます。 ただし、結果が大幅に変わることはほとんどありません。 おそらく、 Atkin Sieveはより良く見えるようになります-現代の暗号化で最もよく使用されるのはこのアルゴリズムです。
*-私にはわからない。 ハルヤビンは最初の解説で長い間知られていることを述べた。
UPD
メモリ消費に関して、説明されているアルゴリズムは次のように動作します。
100万素数、最大RAM
-ブルートフォースディバイダー：〜4Mb
-エラトステネスの変更されたふるい：〜6Mb
1000万素数、最大RAM
-ブルートフォースディバイダー：〜39Mb
-エラトステネスの変更されたふるい：〜61Mb