最初のアルゴリズムは非常に優れており、ProjectEulerで多く使用されています。必要な最大数がわかっている場合は、エラトステネスのふるいを調べることもできます。
素数のリストを維持している場合は、最初のアルゴリズムを改良して、数の平方根まで素数のみで除算することもできます。
これらの2つのアルゴリズム（分割とふるい）を使用すると、問題を解決できるはずです。
編集：コメントに記載されている固定名
エラトステネスのふるい(ページには 20 のプログラミング言語のバリアントが含まれています)よりも小さいすべての素数を生成するには、最も古く、最も単純なソリューションです。
Python の場合:
def iprimes_upto(limit):
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
例：
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
フェルマーの素数性検定はすでに提案されているようですが、私はStructure and Interpretation of Computer Programsに取り組んでおり、別の代替手段としてMiller-Rabin test (セクション 1.2.6、問題 1.28 を参照) も示しています。私はオイラー問題のためにそれをうまく使ってきました。
次の事実に留意してください（MathsChallenge.netから）：
これが私が比較的小さいnに使用するC++関数です：
bool isPrime(unsigned long n)
{
if (n == 1) return false; // 1 is not prime
if (n < 4) return true; // 2 and 3 are both prime
if ((n % 2) == 0) return false; // exclude even numbers
if (n < 9) return true; //we have already excluded 4, 6, and 8.
if ((n % 3) == 0) return false; // exclude remaining multiples of 3
unsigned long r = floor( sqrt(n) );
unsigned long f = 5;
while (f <= r)
{
if ((n % f) == 0) return false;
if ((n % (f + 2)) == 0) return false;
f = f + 6;
}
return true; // (in all other cases)
}
あなたはおそらくあなた自身のより多くの最適化を考えることができます。
これは、エラトステネスのふるいではありませんが、実装が非常に簡単なメソッドの簡単な最適化です。最初にXを2と3で除算してから、j = 1..sqrt（X）/ 6をループして、除算を試みます。 6*j-1および6*j+1による。これにより、2または3で割り切れるすべての数値が自動的にスキップされ、かなり優れた定数係数の加速が得られます。
フェルマーの素数性検定をお勧めします。確率検定ですが、意外と正解することが多いです。そして、ふるいに比べて信じられないほど速いです。
かなり小さい数の場合、sqrt(x) までの x%n は非常に高速で、コーディングも簡単です。
簡単な改善:
テスト 2 と奇数のみ。
テスト 2、3、および 6 の倍数 + または - 1 (2 または 3 以外のすべての素数は 6 +/- 1 の倍数であるため、基本的にすべての偶数とすべての 3 の倍数をスキップするだけです)
素数のみをテストします (sqrt(x) までのすべての素数を計算または保存する必要があります)
sieve メソッドを使用して、任意の制限まですべての素数のリストをすばやく生成できますが、メモリを集中的に使用する傾向があります。6 の倍数のトリックを使用して、メモリ使用量を数値あたり 1/3 ビットに減らすことができます。
6+1 の倍数と 6-1 の倍数に 2 つのビットフィールドを使用する単純な素数クラス (C#) を作成し、単純なルックアップを行います...そして、テストしている数値がふるいの境界外にある場合は、次に、2、3、および 6 +/- 1 の倍数によるテストにフォールバックします。これまでに解決したほとんどのオイラー問題で、大きなふるいを生成すると、その場で素数を計算するよりも実際には時間がかかることがわかりました。KISS主義が再び襲う！
私はふるいを使って小さい素数を事前に計算し、ふるいの範囲外のものについては 2、3、および 6 +/- 1 の倍数によるテストに依存する素数クラスを作成しました。
私はプロジェクトオイラーの問題にも取り組んでおり、実際には、合成数の最高の素因数の検索である＃3（idによる）を終了しました（？の数は600851475143です）。
素数（ここですでに説明したふるい手法）とウィキペディアの素因数分解に関するすべての情報を調べて、ブルートフォース試行除算アルゴリズムを思いついた。
そのため、ルビーを学ぶためにオイラーの問題を実行しているときに、アルゴリズムのコーディングを検討していて、Primeクラスとprime_divisionメソッドを持つIntegerクラスを持つmathnライブラリに出くわしました。なんてクールなんだ。私はこのルビースニペットの問題に対する正しい答えを得ることができました：
require "mathn.rb"
puts 600851475143.prime_division.last.first
このスニペットは、コンソールに正しい答えを出力します。もちろん、この小さな美しさに出くわす前に、私はたくさんの読書と学習をすることになりました、私はそれをみんなと共有すると思っていました...
あなたの権利は単純なものが最も遅いです。あなたはそれをいくらか最適化することができます。
平方根の代わりにモジュラスを使用することを検討してください。あなたの素数を追跡します。6は2と3の倍数であり、4は2の倍数であるため、7を2、3、および5で割るだけで済みます。
Rsliteはエランテノスふるいに言及しました。それはかなり簡単です。私はそれをいくつかの言語で家に持っています。後でそのコードを投稿したい場合は、コメントを追加してください。
これが私のC++です。改善の余地は十分にありますが、動的言語バージョンと比較すると高速です。
// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>
int main(void) {
// using unsigned short.
// maximum value is around 65000
const unsigned short max = 50000;
unsigned short x[max];
for(unsigned short i = 0; i < max; i++)
x[i] = i + 2;
for(unsigned short outer = 0; outer < max; outer++) {
if( x[outer] == 0)
continue;
unsigned short item = x[outer];
for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
unsigned int searchvalue = item * multiplier;
unsigned int maxValue = max + 1;
for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
if(x[maxIndex] != 0) {
maxValue = x[maxIndex];
break;
}
}
for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
if( searchvalue > maxValue )
break;
if( x[searchindex] == searchvalue ) {
x[searchindex] = 0;
break;
}
}
}
}
for(unsigned short printindex = 0; printindex < max; printindex++) {
if(x[printindex] != 0)
std::cout << x[printindex] << "\t";
}
return 0;
}
私が持っているPerlとPythonのコードを見つけたらすぐに投げます。それらはスタイルが似ていますが、線が少ないだけです。
D (Digital Mars) での単純な素数性テストを次に示します。
/**
* to compile:
* $ dmd -run prime_trial.d
* to optimize:
* $ dmd -O -inline -release prime_trial.d
*/
module prime_trial;
import std.conv : to;
import std.stdio : w = writeln;
/// Adapted from: http://www.devx.com/vb2themax/Tip/19051
bool
isprime(Integer)(in Integer number)
{
/* manually test 1, 2, 3 and multiples of 2 and 3 */
if (number == 2 || number == 3)
return true;
else if (number < 2 || number % 2 == 0 || number % 3 == 0)
return false;
/* we can now avoid to consider multiples
* of 2 and 3. This can be done really simply
* by starting at 5 and incrementing by 2 and 4
* alternatively, that is:
* 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
* we don't need to go higher than the square root of the number */
for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
divisor += increment, increment = 6 - increment)
if (number % divisor == 0)
return false;
return true; // if we get here, the number is prime
}
/// print all prime numbers less then a given limit
void main(char[][] args)
{
const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
for (uint i = 0; i < limit; ++i)
if (isprime(i))
w(i);
}
プロジェクト オイラーにとって、素数のリストを持つことは非常に重要です。各問題に使用するリストを維持することをお勧めします。
あなたが探しているのはエラトステネスのふるいだと思います。
私はこのPythonコードが好きです。
def primes(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
return [j for j in xrange(2, limit) if x[j] == 1]
これの変形は、数の因数を生成するために使用できます。
def factors(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
result = []
y = limit-1
while x[y] != 1 :
divisor = x[y]
result.append(divisor)
y /= divisor
result.append(y)
return result
もちろん、数値のバッチを因数分解している場合は、キャッシュを再計算しません。私は一度それを行い、その中でルックアップを行います。
最適化されていませんが、非常に単純な機能です。
function isprime(number){
if (number == 1)
return false;
var times = 0;
for (var i = 1; i <= number; i++){
if(number % i == 0){
times ++;
}
}
if (times > 2){
return false;
}
return true;
}
AKS プライム テスト アルゴリズム:
Input: Integer n > 1
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;
Pythonの別の方法は次のとおりです。
import math
def main():
count = 1
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 2
if __name__ == '__main__':
main()