最初の 10000 個の素数に対する最も効率的なコードは何ですか?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
最初の 10000 個の素数を出力したいと考えています。誰かこれの最も効率的なコードを教えてくれませんか?説明:
- n >10000 の場合、コードの効率が悪くても問題ありません。
- コードのサイズは関係ありません。
- どのような方法でも値をハードコーディングすることはできません。
他のヒント
ふるいをお勧めします。 エラトステネスのふるい または アトキンのふるい。
ふるいまたはエラトステネスは、おそらく素数のリストを見つける最も直感的な方法です。基本的にあなたは:
- 2 から任意の制限 (たとえば 1000) までの数値のリストを書き留めます。
- 取り除かれていない最初の数値 (最初の反復では、これは 2) を選択し、リストからその数値の倍数をすべて取り消します。
- リストの最後に到達するまでステップ 2 を繰り返します。バツ印がされていない数字はすべて素数です。
明らかに、このアルゴリズムの動作を高速化するために実行できる最適化は数多くありますが、これが基本的な考え方です。
アトキンのふるいも同様のアプローチを使用していますが、残念ながら、私はそれについて説明できるほど十分な知識がありません。しかし、私がリンクしたアルゴリズムでは、古い Pentium II-350 で 1000000000 までのすべての素数を計算するのに 8 秒かかることはわかっています。
エラトステネスのふるい ソースコード: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
アトキンのふるいのソースコード: http://cr.yp.to/primegen.html
これは厳密にはハードコーディングの制限に反しているわけではありませんが、非常にそれに近いものです。代わりに、このリストをプログラムでダウンロードして印刷してみてはいかがでしょうか?
ゲートキラー, を追加してみてはいかがでしょうか break それに対して if の中に foreach ループ？そうすれば物事が加速するでしょう たくさん なぜなら、6 が 2 で割り切れる場合は、3 と 5 をチェックする必要がないからです。(私に十分な評判があれば、とにかくあなたのソリューションに賛成票を投じるでしょう :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
Haskell では、エラトステネスのふるいの数学的定義をほぼ一語一語書き留めることができます。素数は、合成数を含まない 1 より大きい自然数であり、合成数は各素数の倍数を列挙することによって見つかります。":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 ほぼ瞬時に行われます。
参考文献:
上記のコードは、オッズのみで動作するように簡単に調整できます。 primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). 。時間計算量は大幅に改善されました (ほぼ ログ 最適値を上回る係数) をツリー状構造に折りたたむことにより、空間の複雑さは 大幅に改善されました による 多段階素数生産, 、 で
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(Haskell では括弧はグループ化に使用され、関数呼び出しは並置するだけで示されます。 (:) です 短所 リストの演算子、および (.) は関数合成演算子です。 (f . g) x = (\y -> f (g y)) x = f (g x)).
@マット:log(log(10000)) は ~2
ウィキペディアの記事より（引用しました） アトキンのふるい:
このふるいは、最大nを使用してプライムを計算します
O(N/log log N)nのみの操作1/2+o(1) 記憶のビット。それは、使用するエラトステネスのふるいよりも少し優れていますO(N)操作と O(N1/2（log log n）/log n）メモリのビット (A.O.L.アトキン、D.J.バーンスタイン、2004). 。これらの漸近計算の複雑さには、ホイールファクター化などの単純な最適化、計算をより小さなブロックに分割することが含まれます。
漸近的な計算複雑性を考慮すると、 O(N) （エラトステネスの場合）そして O(N/log(log(N))) (アトキンの場合) とは言えません (小さい場合) N=10_000) 実装された場合、どのアルゴリズムが高速になるか。
アヒム・フラメンカンプが書いた エラトステネスのふるい:
によって引用：
@num1
約10^9の間隔では、確かに10^10を超えると、エラトステネスのふるいは、還元できないバイナリ二次形式を使用するアトキンスとバーンスタインのふるいにかけられます。背景の情報については、Wのパラグラフ5については、彼らの論文を参照してください。ゴールウェイの博士号論文。
したがって、 10_000 エラトステネスのふるいはアトキンのふるいよりも速い可能性があります。
OPに答えるコードは次のとおりです プライムシーブ.c （によって引用 num1)
GMP を使用すると、次のように記述できます。
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
私の 2.33GHz Macbook Pro では、次のように実行されます。
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
同じラップトップで 1,000,000 の素数を計算する:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP はこの種のものに対して高度に最適化されています。独自のアルゴリズムを作成してアルゴリズムを本当に理解したい場合を除き、C で libGMP を使用することをお勧めします。
まったく効率的ではありませんが、正規表現を使用して素数をテストできます。
/^1?$|^(11+?)\1+$/
これは、以下で構成される文字列について、次のことをテストします。 k “1「」さん、 k は 素数ではない (すなわち、文字列が 1 つの「」で構成されているかどうか1「」または任意の数の「1”として表現できる n-ary製品）。
で見つかったコードを適応させました コードプロジェクト 以下を作成するには:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
ASP.NET サーバーでこれをテストすると、ルーチンの実行に約 1 分かかりました。
これは、数日前に PowerShell で作成したエラトステネスのふるいです。返される素数の数を識別するためのパラメーターがあります。
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
エラトステネスのふるい シンプルさとスピードの点で、これが最適な方法です。C での私の実装
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
素数を見つけるための CPU 時間 (Pentium Dual Core E2140 1.6 GHz、シングルコア使用)
~ 4 秒 (lim = 100,000,000)
適応し、継続する ゲートキラー, これが私が使用した最終バージョンです。
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
基本的には同じですが、「Sqrt で中断」という提案を追加し、より適切になるようにいくつかの変数を変更しました。(私はオイラーに取り組んでいたので、10001 番目の素数が必要でした)
ふるいは不正解のようです。ふるいは素数を与えます まで 数 N, ではなく、 最初のN 素数。@Imran または @Andrew Szeto を実行すると、N までの素数が得られます。
結果セットの特定のサイズに達するまで、ますます大きな数値に対してふるいを試し続け、すでに取得した数値のキャッシュを使用する場合、ふるいはまだ使用できるかもしれませんが、それでも@Patのようなソリューションよりも高速ではないと思います。
Pythonで
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
の BenGoldberg が言及した deque sieve アルゴリズム これは非常にエレガントであるだけでなく、(純粋に学術的な演習であるアトキンのふるいとは異なり) 実際に役立つ可能性があるため、詳しく見てみる価値があります。
deque sieve アルゴリズムの背後にある基本的な考え方は、現在「アクティブな」素因数ごとに少なくとも 1 つの別個の倍数を含むのに十分な大きさの小さなスライドふるいを使用することです。移動するふるいによって現在表されている最小数を二乗が超えない素数。SoE とのもう 1 つの違いは、deque sieve がブール値ではなく実際の因子を複合体のスロットに格納することです。
このアルゴリズムは、必要に応じてふるいウィンドウのサイズを拡張し、ふるいが CPU の L1 キャッシュの容量を大幅に超え始めるまで、広範囲にわたってほぼ均一なパフォーマンスを実現します。完全に適合する最後の素数は 25,237,523 (1,579,791 番目の素数) であり、これはアルゴリズムの妥当な動作範囲の大まかな数値を示します。
このアルゴリズムは非常にシンプルかつ堅牢で、セグメント化されていないエラトステネスのふるいよりもはるかに広い範囲にわたって均一なパフォーマンスを発揮します。後者は、ふるいがキャッシュに完全に収まる限り、はるかに高速です。バイトサイズのブール値を含むオッズのみのふるいの場合は最大 2^16。その後、そのパフォーマンスはますます低下しますが、ハンディキャップにもかかわらず (少なくとも C/C++、Pascal、Java/C# などのコンパイル言語では) 常に deque よりも大幅に高速なままです。
ここに C# での deque sieve アルゴリズムのレンダリングを示します。なぜなら、この言語は、多くの欠陥があるにもかかわらず、非常に面倒で衒学的な C++ よりも、アルゴリズムのプロトタイピングや実験にとってはるかに実用的であると私が思うからです。 （サイドノート：無料のものを使っています LINQパッド これにより、プロジェクト、メイクファイル、ディレクトリなどのセットアップに煩わしさを感じることなく、すぐに作業を始めることができ、Python プロンプトと同程度の対話性が得られます。
C# には明示的な deque 型はありませんが、プレーンな deque 型はありません。 List<int> アルゴリズムをデモンストレーションするには十分に機能します。
注記：このバージョンでは素数の両端キューを使用しません。n 個の素数から sqrt(n) を取り出すのは単純に意味がないからです。100 個の素数を削除して 9900 個を残すことに何の意味があるでしょうか?少なくともこの方法では、すべてのプライムがきちんとしたベクターに収集され、さらなる処理の準備が整います。
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
以下に 2 つのヘルパー関数を示します。
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
おそらくこのアルゴリズムを理解する最も簡単な方法は、セグメント サイズ 1 の特別にセグメント化されたエラトステネスのふるいで、素数がセグメントの端を越えて発射したときに停止するオーバーフロー領域を伴うものとして想像することです。ただし、セグメントの単一セル（別名、 sieve[0]）は、オーバーフローエリアの一部だったときに轢かれてしまったので、私たちがそこに着いたときにはすでにふるいにかけられていました。
で表される数字は、 sieve[0] で開催されます sieve_base, 、 それでも sieve_front または window_base また、Ben のコードやセグメント化/ウィンドウ化された sieve の実装と類似した名前を付けることもできます。
もし sieve[0] ゼロ以外の値が含まれている場合、その値は係数になります sieve_base, 、したがって複合として認識できます。セル 0 はその係数の倍数であるため、単純に 0 にその係数を加えた次のホップを計算するのは簡単です。そのセルがすでに別の因子によって占有されている場合は、単純にその因子を再度追加し、現在他の因子が配置されていない因子の倍数が見つかるまで同様に繰り返します (必要に応じてふるいを拡張します)。これは、通常のセグメント化されたふるいのように、あるセグメントから次のセグメントまでのさまざまな素数の現在の作業オフセットを保存する必要がないことも意味します。要因を見つけるたびに、 sieve[0], 、現在の動作オフセットは 0 です。
現在の素数は次のように機能します。プライムは、ストリーム内でそれ自体が発生した後にのみ最新になることができます (すなわち、因子でマークされていないため、素数として検出されたとき)、その瞬間まで最新のままになります。 sieve[0] その広場に到達します。通常の SoE と同様に、この素数の下位倍数はすべて、より小さい素数のアクティビティによって打ち消されたに違いありません。しかし、平方の唯一の因数は素数そのものであり、この時点ではまだ流通していないため、より小さな素数は平方から外れることはできません。これは、この場合にアルゴリズムによって実行されるアクションを説明しています sieve_base == current_prime_squared (つまり sieve[0] == 0, 、 ところで）。
さて、ケース sieve[0] == 0 && sieve_base < current_prime_squared 簡単に説明すると、だということだ sieve_base 現在の素数よりも小さい素数の倍数にすることはできません。そうでない場合は、複合としてマークされます。I の値が現在の素数の 2 乗より小さいため、I も現在の素数の倍数以上にすることはできません。したがって、それは新しい素数でなければなりません。
このアルゴリズムは明らかにエラトステネスのふるいからインスピレーションを得ていますが、同様に明らかに大きく異なります。エラトステネスのふるいは、その基本操作の単純さから優れた速度を引き出します。長時間にわたって実行されるのは、操作の各ステップで 1 回のインデックス追加と 1 回のストアだけです。
これは、ushort 範囲の因子素数をふるい分けるために通常使用する、単純でセグメント化されていないエラトステネスのふるいです。2^16まで。この投稿では、次のように置き換えることで 2^16 を超えて動作するように変更しました。 int のために ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
最初の 10000 個の素数をふるい分ける場合、通常の L1 キャッシュの 32 キロバイトを超えますが、関数は依然として非常に高速です (C# であっても 1 ミリ秒の何分の一)。
このコードを deque sieve と比較すると、deque sieve の操作がはるかに複雑であることが簡単にわかります。また、常に可能な限り短い範囲の交差を連続して実行するため、オーバーヘッドを効果的に償却することができません。 (すでに取り消されているすべての倍数をスキップした後、1 つの取り消しのみ)。
注記：C# コードは使用します int の代わりに uint 新しいコンパイラには、標準以下のコードを生成する習慣があるためです。 uint, おそらく、人々を符号付き整数に近づけるためでしょう...上記のコードの C++ バージョンでは、 unsigned 全体を通して、自然に。ベンチマークはおそらく適切な deque 型に基づく必要があったため、C++ で行う必要がありました (std::deque<unsigned>;を使用してもパフォーマンスの向上はありませんでした unsigned short）。私の Haswell ラップトップ (VC++ 2015/x64) の数値は次のとおりです。
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
注記：C# の時間は C++ のタイミングのほぼ 2 倍であり、これは C# にとっては非常に優れており、これは次のことを示しています。 List<int> デクと罵られても屈しない。
単純な sieve コードは、すでに通常の動作範囲を超えて動作しているにもかかわらず (L1 キャッシュ サイズが 50% を超え、キャッシュ スラッシングが伴う)、デックを水から吹き飛ばします。ここで最も重要な部分は、ふるいにかけられた素数の読み取りであり、これはキャッシュの問題の影響をあまり受けません。いずれにしても、関数は因子の因子をふるい分けるために設計されました。3 レベルの sieve 階層のレベル 0 であり、通常は数百の因子のみ、または少数の数千の因子のみを返す必要があります。だからこそそのシンプルさ。
セグメント化されたふるいを使用し、ふるいにかけられた素数を抽出するコードを最適化することで、パフォーマンスを 1 桁以上向上させることができます (mod 3 をステップにして 2 回展開するか、mod 15 を実行して 1 回展開します)。さらに、さらに多くのパフォーマンスを絞り出すことができます。すべてのトリミングを備えた mod 16 または mod 30 ホイールを使用してコードを作成します (つまり、すべての残基の完全な展開)。そのようなことは私の答えで説明されています 素数の位置を調べる コードレビューでは、同様の問題が議論されました。しかし、1 回限りのタスクでミリ秒未満の時間を改善する意味を理解するのは困難です...
物事を少し客観的に見るために、最大 100,000,000 をふるい分けるための C++ のタイミングを次に示します。
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
対照的に、いくつかの付加機能を備えた C# のセグメント化されたふるいは、同じ仕事を 95 ミリ秒で実行します (現時点では C# でのみコードチャレンジを行っているため、C++ のタイミングは利用できません)。
Python のようなインタプリタ型言語では、すべての操作に大きなコストがかかり、インタプリタのオーバーヘッドによって、予測と予測による違いがすべて矮小化されるため、物事は明らかに異なって見えるかもしれません。予測を誤った分岐またはサブサイクル演算 (シフト、加算) とマルチサイクル演算 (乗算、さらには除算も)。これでは、エラトステネスのふるいのシンプルさの利点が損なわれることは間違いなく、これにより、deque ソリューションがもう少し魅力的なものになる可能性があります。
また、このトピックの他の回答者によって報告されたタイミングの多くは、おそらく次のような理由で占められています。 出力時間. 。それはまったく異なる戦争であり、私の主な武器は次のような単純なクラスです。
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
10000 個の (ソートされた) 数値を書き込むのにかかる時間は 1 ミリ秒未満です。これは、最小限の手間とゼロのオーバーヘッドで、コーディング課題の提出にテキストを含めることを目的としているため、静的クラスです。
一般的に、私はそれがそうであることがわかりました 多くの すべてを一緒に混ぜ合わせるのではなく、集中した作業をバッチ全体で実行すると、より高速になります。つまり、特定の範囲をふるいにかけ、すべての素数をベクトル/配列に抽出し、次に配列全体を吹き出し、次の範囲をふるいにかけ、というようになります。特定のタスクに焦点を当てた個別の機能を用意すると、組み合わせが容易になり、再利用が可能になり、開発/テストが容易になります。
これは私の VB 2008 コードです。職場のラップトップで 10,000,000 未満の素数を 1 分 27 秒ですべて検索します。偶数をスキップし、テスト番号の 2 乗未満の素数のみを探します。0 からセンチナル値までの素数を見つけるようにのみ設計されています。
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
次の Mathcad コードは、最初の 100 万個の素数を 3 分以内に計算しました。
これはすべての数値に浮動小数点 double を使用し、基本的に解釈されることに留意してください。構文が明確であることを願っています。
ここでは、SoE の形式を使用した C++ ソリューションを示します。
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
このバージョンの Sieve は無制限に素数を計算できることに注意してください。
STL にも注意してください。 deque かかります O(1) 演奏する時間 push_back, pop_front, 、およびサブスクリプトによるランダムアクセス。
の resize 操作には時間がかかります O(n) 時間、場所 n 追加される要素の数です。この関数の使用方法により、これは小さな定数として扱うことができます。
の本体 while ループイン my_insert 実行される O(log log n) 回、どこで n 変数に等しい maybe_prime. 。これは、 while の素因数ごとに 1 回 true と評価されます。 maybe_prime. 。見る "除数関数」ウィキペディアにあります。
回数を掛ける my_insert が呼び出され、それがかかることを示します O(n log log n) リストする時間 n 素数...これは当然のことながら、エラトステネスの篩が持つと考えられる時間計算量です。
ただし、このコードでは は 効率的ではありませんが、 最も効率的な...素数生成に特化したライブラリを使用することを強くお勧めします。 プライムシーブ. 。本当に効率的で適切に最適化されたソリューションでは、Stackoverflow に入力したいコードよりも多くのコードが必要になります。
エラトステネスのふるいを使用すると、「既知の」素数アルゴリズムと比較して、計算がかなり高速になります。
Wiki の疑似コードを使用することにより (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）、C#で解決策を得ることができます。
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) には 2 秒と 330 ミリ秒かかります。
注記:値はハードウェア仕様によって異なる場合があります。
私は多くの素数を計算するプログラムを書くのに時間を費やしています。これは、最初の 1.000.000.000 個の素数を含むテキスト ファイルを計算するために使用するコードです。ドイツ語ですが、興味深いのはその方法です。 calcPrimes(). 。素数は Primzahlen という配列に保存されます。計算は 64 ビット整数を使用するため、64 ビット CPU をお勧めします。
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
私はPythonを学び始めたばかりなので、Pythonを使用してこれを書きましたが、完全に問題なく動作します。で述べたのと同じように、このコードによって10,000番目の素数が生成されます。 http://primes.utm.edu/lists/small/10000.txt. 。かどうかを確認するには n 素数かそうでないか、除算する n からの数字によって 2 に sqrt(n). 。この範囲の数値のいずれかが完全に分割される場合 n それならプライムじゃないよ。
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
私は素数を見つけることに約1年間取り組んできました。これが私が最も速いと感じたものです:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
2 から開始して 2147483629 に到達するには、1902465190909 ナノ秒かかります。
ラップトップで0.049655秒で最初の10,000プライムを見つけた私のコードは、6秒未満で最初の1,000,000プライム、15秒で最初の2,000,000を見つけます
ちょっとした説明。この方法では、素数を見つけるために 2 つの手法を使用します。
- まず第一に、素数以外の数値は素数の倍数の合成であるため、このコードは、任意の数値ではなく、テスト数値をより小さい素数で除算することによってテストします。これにより、計算が 4 桁の数値の場合は少なくとも 10 分の 1、さらに 4 桁の数値の場合はさらに少なくなります。より大きな数字
- 次に、素数で割る以外に、テスト対象の数値の根以下の素数で割るだけなので、計算がさらに大幅に削減されます。これは、数値の根より大きい数値には対応する数値があるため機能します。は数値のルートより小さい必要がありますが、ルートより小さい数値はすべてすでにテスト済みなので、テスト対象の数値のルートより大きい数値を気にする必要はありません。
最初の 10,000 個の素数の出力例
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
これがC言語のコードです。1つ、その後10,000を入力して、最初の10,000プライムを印刷します。
編集：これに数学ライブラリが含まれていることを忘れていました。Windows または Visual Studio を使用している場合は問題ありませんが、Linux では -lm 引数を使用してコードをコンパイルする必要があります。そうしないとコードが機能しない可能性があります。
例：gcc -Wall -o "%e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
ここに私が作成したコードがあります:
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
Javascript で Array.prototype.find() メソッドを使用します。2214.486ミリ秒
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
いくつかヒントを与えることができるので、それを実行する必要があります。
- それぞれの数値について、その数値の半分を求めます。例えば。21 をチェックする場合は、範囲 2 ～ 10 を除算して余りを取得するだけです。
- 奇数の場合は奇数で除算するだけでよく、その逆も同様です。21の場合は3、5、7、9のみで割ります。
私がこれまでに見つけた最も効率的な方法。
最初の10000プライムのみが必要なので、複雑なアルゴリズムをコーディングするのではなく、次のことを提案します
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
必要に応じてコールがプライムになります
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
