質問
私たちは仕事で少し楽しんでいます。それはすべて、Hackintoshをセットアップする男の1人から始まり、(ほぼ)同じ仕様のWindowsボックスよりも高速かどうか疑問に思っていました。そこで、私たちはそれのための小さなテストを書くことにしました。シンプルな素数計算機。 Javaで書かれており、最初のn個の素数を計算するのにかかる時間を教えてくれます。
以下の最適化されたバージョン-約6.6秒かかります
public class Primes {
public static void main(String[] args) {
int topPrime = 150000;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
}
Hackintosh対PCの全体のプロットをほとんど失い、最適化を少し楽しんでいます。最適化なしの最初の試み(上記のコードにはいくつかあります)は、最初の150000の素数を見つけるために約52.6分実行されました。この最適化は約47.2分で実行されます。
実行して結果を投稿する場合は、emを貼り付けます。
実行しているPCの仕様は、Pentium D 2.8GHz、2GB RAM、Ubuntu 8.04を実行しています。
これまでの最適化は、現在の平方根であり、最初にジェイソンZが言及しました。
解決
まあ、2、3の簡単な最適化を行うことができます。 まず、現在の番号の半分まで各番号を試す必要はありません。
代わりに、現在の数の平方根までしか試すことができません。
他の最適化は、BPがひねりをつけて言ったことです。 の代わりに
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
使用
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
これにより、処理速度が大幅に向上します。
編集:
Joe Pinedaの好意によるさらなる最適化:
変数<!> quot; top <!> quot;を削除します。
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
この最適化により実際に速度が向上する場合は、javaになります。 平方根の計算には、2つの数値を乗算するのに比べて時間がかかります。ただし、乗算をforループに移動するため、これは単一ループごとに実行されます。そのため、このCOULDは、Javaの平方根アルゴリズムの速度に応じて速度を低下させます。
他のヒント
これは、1986年頃にターボパスカルで8 Mhz 8088を使用したときのふるいよりも少し悪いです。しかし、それは最適化の後です:)
昇順でそれらを検索しているので、すでに見つかった素数のリストを保持し、それらに対する分割可能性のみをチェックすることができます。要因。これを、現在の数値の平方根上の因子をチェックしないことに関する以前のヒントと組み合わせると、非常に効率的な実装が得られます。
こちらは高速でシンプルなソリューションです:
- 100000未満の素数の検索。 5592で9592が見つかりました
- 1000000未満の素数の検索。 78498は20ミリ秒で見つかりました
- 10000000未満の素数の検索。 664579は143ミリ秒で見つかりました
- 100000000未満の素数の検索。 5761455は2024ミリ秒で見つかりました
-
1000000000未満の素数の検索。 50847534は23839ミリ秒で見つかりました
//returns number of primes less than n private static int getNumberOfPrimes(final int n) { if(n < 2) return 0; BitSet candidates = new BitSet(n - 1); candidates.set(0, false); candidates.set(1, false); candidates.set(2, n); for(int i = 2; i < n; i++) if(candidates.get(i)) for(int j = i + i; j < n; j += i) if(candidates.get(j) && j % i == 0) candidates.set(j, false); return candidates.cardinality(); }
Sieve of Eratosthenesを使用してPythonで最初の150000の素数を生成するには、1秒(2.4 GHz)未満です。
#!/usr/bin/env python
def iprimes_upto(limit):
"""Generate all prime numbers less then limit.
http://stackoverflow.com/questions/188425/project-euler-problem#193605
"""
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
def sup_prime(n):
"""Return an integer upper bound for p(n).
p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)
where p(n) is the n-th prime.
http://primes.utm.edu/howmany.shtml#2
"""
from math import ceil, log
assert n >= 13
pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
return int(ceil(pn))
if __name__ == '__main__':
import sys
max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
print("Generated %d primes" % len(primes))
n = 100
print("The first %d primes are %s" % (n, primes[:n]))
例:
$ python primes.py
Generated 153465 primes
The first 100 primes are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
C#の場合:
class Program
{
static void Main(string[] args)
{
int count = 0;
int max = 150000;
int i = 2;
DateTime start = DateTime.Now;
while (count < max)
{
if (IsPrime(i))
{
count++;
}
i++;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
if (n < 4)
return true;
if (n % 2 == 0)
return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
出力:
合計所要時間:2.087秒
素数を探すより良い方法があることに留意してください...
このループを使用できると思います:
for (int i = 2; i < top; i++)
2以外のすべての素数が偶数で割り切れないため、カウンター変数iが3から奇数にのみmodを実行するようにします。
変数primeの再宣言を行います
while (count < topPrime) {
boolean prime = true;
ループ内で非効率にしますか? (Javaはこれを最適化すると思うので、それは問題ではないと思います)
boolean prime;
while (count < topPrime) {
prime = true;
C#
これは、3より大きいすべての素数が6n + 1または6n-1の形式であるという事実を利用します。
これは、ループを通過するたびに1ずつ増加するのに比べて、4〜5%の速度の増加でした。
class Program
{
static void Main(string[] args)
{
DateTime start = DateTime.Now;
int count = 2; //once 2 and 3
int i = 5;
while (count < 150000)
{
if (IsPrime(i))
{
count++;
}
i += 2;
if (IsPrime(i))
{
count++;
}
i += 4;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
//if (n < 4)
//return true;
//if (n % 2 == 0)
//return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
私が最適化に取り組むのは、あまりにも不可解なトリックを避けるためです。私はI-GIVE-TERRIBLE-ADVICEによって与えられたトリックを使用します。私はそれを知っていて忘れていました...:-)
public class Primes
{
// Original code
public static void first()
{
int topPrime = 150003;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("\n-- First");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
// My attempt
public static void second()
{
final int wantedPrimeNb = 150000;
int count = 0;
int currentNumber = 1;
int increment = 4;
int lastPrime = 0;
long start = System.currentTimeMillis();
NEXT_TESTING_NUMBER:
while (count < wantedPrimeNb)
{
currentNumber += increment;
increment = 6 - increment;
if (currentNumber % 2 == 0) // Even number
continue;
if (currentNumber % 3 == 0) // Multiple of three
continue;
int top = (int) Math.sqrt(currentNumber) + 1;
int testingNumber = 5;
int testIncrement = 2;
do
{
if (currentNumber % testingNumber == 0)
{
continue NEXT_TESTING_NUMBER;
}
testingNumber += testIncrement;
testIncrement = 6 - testIncrement;
} while (testingNumber < top);
// If we got there, we have a prime
count++;
lastPrime = currentNumber;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
System.out.println("\n-- Second");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
}
public static void main(String[] args)
{
first();
second();
}
}
はい、ラベル付き継続を使用しました。初めてJavaで試してみました...
最初の数個の素数の計算をスキップすることは知っていますが、それらはよく知られているので、再計算する意味はありません。 :-)必要に応じて出力をハードコーディングできます!横に、それはとにかく決定的なエッジを与えません。
結果:
-最初
最後の素数= 2015201
合計時間= 4.281
-秒
最後の素数= 2015201
合計時間= 0.953
悪くない。少し改善されるかもしれませんが、最適化が多すぎると良いコードが殺される可能性があります。
奇数を評価するだけで、内側のループを2倍速くできるはずです。これが有効なJavaかどうかはわかりませんが、私はC ++に慣れていますが、適応できると確信しています。
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
私はこれをF#で試してみることにしました。 2.2Ghz Core 2 Duoでエラトステネスのふるいを使用すると、約200ミリ秒で2..150,000を実行します。自己を呼び出すたびに、リストから現在の倍数が削除されるため、処理が進むにつれて高速になります。これはF#での最初の試みの1つなので、建設的なコメントを歓迎します。
let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
match sieve with
| [] -> sieve
| _ when sqrt(float(max)) < float sieve.[0] -> sieve
| _ -> let prime = sieve.[0]
let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
let result = getPrimes filtered max
prime::result // The filter removes the prime so add it back to the primes result.
let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds
Miller-Rabinの方が高速になるはずです。十分な連続数をテストすると、確定的になりますが、気にしません。ランダム化されたアルゴリズムが、その失敗率がCPUのしゃっくりが間違った結果を引き起こす可能性と等しくなるポイントに達すると、それはもはや重要ではなくなります。
ここに私のソリューションがあります...かなり高速です... Vista64で私のマシン(core i7 @ 2.93Ghz)で3秒で1〜10,000,000の間の素数を計算します。
私のソリューションはCですが、私はプロのCプログラマではありません。アルゴリズムとコード自体を自由に批判してください:)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880
//list of calculated primes
__int64* primes;
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;
//Prints all of the calculated primes
void PrintPrimes()
{
__int64 i;
for(i=0; i<primeCount; i++)
{
printf("%d ", primes[i]);
}
}
//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
register __int64 i;
double square;
primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
primeCount = 0;
arraySize = ARRAYMULT;
//we provide the first prime because its even, and it would be convenient to start
//at an odd number so we can skip evens.
primes[0] = 2;
primeCount++;
for(i=3; i<max; i+=2)
{
int j;
square = sqrt((double)i);
//only test the current candidate against other primes.
for(j=0; j<primeCount; j++)
{
//prime divides evenly into candidate, so we have a non-prime
if(i%primes[j]==0)
break;
else
{
//if we've reached the point where the next prime is > than the square of the
//candidate, the candidate is a prime... so we can add it to the list
if(primes[j] > square)
{
//our array has run out of room, so we need to expand it
if(primeCount >= arraySize)
{
int k;
__int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));
for(k=0; k<primeCount; k++)
{
newArray[k] = primes[k];
}
arraySize += ARRAYMULT;
free(primes);
primes = newArray;
}
//add the prime to the list
primes[primeCount] = i;
primeCount++;
break;
}
}
}
}
}
int main()
{
int max;
time_t t1,t2;
double elapsedTime;
printf("Enter the max number to calculate primes for:\n");
scanf_s("%d",&max);
t1 = time(0);
CalcPrime(max);
t2 = time(0);
elapsedTime = difftime(t2, t1);
printf("%d Primes found.\n", primeCount);
printf("%f seconds elapsed.\n\n",elapsedTime);
//PrintPrimes();
scanf("%d");
return 1;
}
ここに私の見解があります。プログラムはCで書かれており、ラップトップ(Core 2 Duo、1 GB Ram)で50ミリ秒かかります。計算されたすべての素数を配列に保持し、数のsqrtまでのみ可分性を試しています。もちろん、配列が大きくなりすぎてsegフォールトが発生するため、非常に多数の素数(100000000で試行)が必要な場合、これは機能しません。
/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000
main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;
primes[0] = 2;
count = 1;
for(i = 3; count < TOTALPRIMES; i+= 2){
isPrime = 1;
//check divisiblity only with previous primes
for(j = 0; j < count; j++){
cpr = primes[j];
if(i % cpr == 0){
isPrime = 0;
break;
}
if(cpr*cpr > i){
break;
}
}
if(isPrime == 1){
//printf("Prime: %d\n", i);
primes[count] = i;
count++;
}
}
printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}
$ time ./a.out Last prime = 163841 real 0m0.045s user 0m0.040s sys 0m0.004s
@ Mark Ransom-これがJavaコードかどうかわからない
彼らはおそらくうめき声をあげますが、Javaを信頼することを学んだパラダイムを使用して書き直したいと思いました。彼らはいくつかの楽しみを持っていると言いました。返された結果セット、短い用事を取る前にメモ帳で一度限りの結果セットのドット値()をリストタイプにキャストします
===============未テストコードの開始================
package demo;
import java.util.List;
import java.util.HashSet;
class Primality
{
int current = 0;
int minValue;
private static final HashSet<Integer> resultSet = new HashSet<Integer>();
final int increment = 2;
// An obvious optimization is to use some already known work as an internal
// constant table of some kind, reducing approaches to boundary conditions.
int[] alreadyKown =
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541
};
// Trivial constructor.
public Primality(int minValue)
{
this.minValue = minValue;
}
List calcPrimes( int startValue )
{
// eliminate several hundred already known primes
// by hardcoding the first few dozen - implemented
// from prior work by J.F. Sebastian
if( startValue > this.minValue )
{
// Duh.
current = Math.abs( start );
do
{
boolean prime = true;
int index = current;
do
{
if(current % index == 0)
{
// here, current cannot be prime so break.
prime = false;
break;
}
while( --index > 0x00000000 );
// Unreachable if not prime
// Here for clarity
if ( prime )
{
resultSet dot add ( or put or whatever it is )
new Integer ( current ) ;
}
}
while( ( current - increment ) > this.minValue );
// Sanity check
if resultSet dot size is greater that zero
{
for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
return resultSet;
}
else throw an exception ....
}
===============未テストコードの終了================
ハッシュセットを使用すると、結果をBツリーとして検索できるため、マシンが故障し始めるまで結果を積み重ねることができ、その開始点をテストの別のブロックに使用できます==コンストラクターの値として使用される1つの実行の終了別の実行では、ディスクへの永続的な作業がすでに完了しており、増分フィードフォワード設計が可能です。すぐに燃え尽きます。ループロジックには分析が必要です。
パッチ(プラスsqrtを追加):
if(current % 5 == 0 )
if(current % 7 == 0 )
if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}
// and - new work this morning:
package demo;
/**
*
* Buncha stuff deleted for posting .... duh.
*
* @author Author
* @version 0.2.1
*
* Note strings are base36
*/
public final class Alice extends java.util.HashSet<java.lang.String>
{
// prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
// using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
public static void main(java.lang.String[] args)
{
try
{
final long start=System.currentTimeMillis();
// VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
final java.lang.Integer upperBound=new java.lang.Integer(40000);
int index = upperBound.intValue();
final java.util.HashSet<java.lang.String>hashSet
= new java.util.HashSet<java.lang.String>(upperBound.intValue());//
// Arbitraily chosen value, based on no idea where to start.
java.math.BigInteger probablePrime
= new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
do
{
java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
{
probablePrime = nextProbablePrime;
if( ( index % 100 ) == 0x00000000 )
{
// System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
continue;
}
else
{
continue;
}
}
else
{
throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
Integer.toString(upperBound.intValue() - index)));
}
}
while(--index > 0x00000000);
System.err.println(Long.toString( System.currentTimeMillis() - start));
}
catch(java.security.NoSuchAlgorithmException nsae)
{
// Never happen
return;
}
catch(java.lang.StackOverflowError soe)
{
// Might happen
System.out.println(soe.getMessage());//
return;
}
}
}// end class Alice
素数に関するこのブログエントリを読み始めたときに、このコードをマシンのどこかに見つけました。 コードはC#であり、私が使用したアルゴリズムは、おそらくウィキペディアのどこかにありますが、私の頭からのものです。 ;) とにかく、最初の150000の素数を約300ミリ秒で取得できます。最初のn個の奇数の合計がn ^ 2に等しいことを発見しました。繰り返しになりますが、おそらくウィキペディアのどこかにこの証拠があります。これを知っているので、平方根を計算する必要がないアルゴリズムを書くことができますが、素数を見つけるために増分的に計算する必要があります。したがって、N番目の素数が必要な場合、このアルゴリズムは前に(N-1)個の素数を見つける必要があります!そこにあります。お楽しみください!
//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
if (count == 0)
return 0;
if (count == 1)
{
if (listPrimes != null)
{
if (!getLast || (count == 1))
listPrimes.Add(2);
}
return count;
}
ulong currentSquare = 1;
ulong nextSquare = 9;
ulong nextSquareIndex = 3;
ulong primesCount = 1;
List dividers = new List();
//Only check for odd numbers starting with 3.
for (ulong curNumber = 3; (curNumber (nextSquareIndex % div) == 0) == false)
dividers.Add(nextSquareIndex);
//Move to next square number
currentSquare = nextSquare;
//Skip the even dividers so take the next odd square number.
nextSquare += (4 * (nextSquareIndex + 1));
nextSquareIndex += 2;
//We may continue as a square number is never a prime number for obvious reasons :).
continue;
}
//Check if there is at least one divider for the current number.
//If so, this is not a prime number.
if (dividers.Exists(div => (curNumber % div) == 0) == false)
{
if (listPrimes != null)
{
//Unless we requested only the last prime, add it to the list of found prime numbers.
if (!getLast || (primesCount + 1 == count))
listPrimes.Add(curNumber);
}
primesCount++;
}
}
return primesCount;
}
私の貢献は次のとおりです。
マシン:2.4GHz Quad-Core i7 w / 8GB RAM @ 1600MHz
コンパイラ:clang++ main.cpp -O3
ベンチマーク:
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100
Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000
Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000
Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000
Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000
Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000
Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000
Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000
Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000
Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$
出典:
#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
if(argc == 1) {
cout << "Please enter a number." << "\n";
return 1;
}
long n = atol(argv[1]);
long i;
long j;
long k;
long c;
long sr;
bool * a = (bool*)malloc((size_t)n * sizeof(bool));
for(i = 2; i < n; i++) {
a[i] = true;
}
clock_t t = clock();
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
a[j] = false;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
//cout << i << " ";
c++;
}
}
cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}
これは、エラストテネスのふるいアプローチを使用します。知識がある限り、できる限り最適化しました。改善を歓迎します。