Primzahl Berechnung Spaß
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wir haben ein bisschen Spaß hier bei der Arbeit. Es begann alles mit einer der Jungs Einstellung eines Hackintosh und wir fragten uns, ob es schneller als ein Windows-Box von (fast) gleichen Spezifikationen, die wir haben. Also beschlossen wir, einen kleinen Test für sie zu schreiben. Nur ein einfacher Primzahlrechner. Es ist in Java geschrieben und erzählt uns die Zeit, die ersten n Primzahlen berechnen nimmt.
Optimierte Version unten - jetzt nimmt ~ 6.6secs
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);
}
}
Wir haben so ziemlich die Handlung des ganzen Hackintosh vs PC Sache verloren und haben nur etwas Spaß mit ihm zu optimieren. Erster Versuch ohne Optimierungen (der obige Code hat ein paar) lief um 52.6min die ersten 150000 Primzahlen zu finden. Diese Optimierung läuft um 47.2mins.
Wenn Sie ein zu gehen haben wollen und die Ergebnisse zu veröffentlichen, dann halten em.
Specs für den PC Ich bin es läuft auf Pentium D 2,8 GHz sind, 2GB RAM, läuft Ubuntu 8.04.
Best-Optimierung bisher die Quadratwurzel von Strom gewesen, die zuerst von Jason Z genannt.
Lösung
Nun, ich sehe ein paar schnelle Optimierungen, die getan werden kann. Zuerst Sie müssen nicht jede Zahl versuchen, bis zur Hälfte der aktuellen Zahl.
Stattdessen müssen Sie nur auf die Quadratwurzel der aktuellen Anzahl versuchen auf.
Und die andere Optimierung war das, was BP sagte mit einem Twist: Statt
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
Verwendung
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Dies sollte eine ganze Menge Dinge beschleunigen.
Bearbeiten
Weitere Optimierung mit freundlicher Genehmigung von Joe Pineda:
Entfernen Sie die Variable "top".
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Wenn diese Optimierung in der Tat Geschwindigkeit erhöht, ist bis zu Java.
Berechnung der Quadratwurzel nimmt viel Zeit im Vergleich zu Multiplikation zweier Zahlen. Aber da wir die Multiplikation in der for-Schleife bewegen, diese jede einzelne Schleife getan. So könnte diese Dinge verlangsamen, je nachdem, wie schnell die Quadratwurzel-Algorithmus in Java ist.
Andere Tipps
Das ist ein bisschen schlechter als mein Sieb im Jahr 1986 auf ein 8 Mhz 8088 in Turbo Pascal hat oder so. Aber das war nach Optimierungen:)
Da Sie für sie in aufsteigender Reihenfolge sind, können Sie eine Liste der Primzahlen halten haben Sie bereits gefunden und prüfen nur für Teilbarkeit gegen sich, da alle Nicht-Primzahlen können auf eine Liste von weniger prime reduziert werden Faktoren. Kombiniert man dies mit der vorherigen Spitze über keine Faktoren über die Quadratwurzel der aktuellen Anzahl prüft, und Sie finden sich eine verflixt effiziente Implementierung haben.
Hier ist eine schnelle und einfache Lösung:
- Finding Primzahlen weniger als 100000; 9592 wurden in 5 ms gefunden
- Finding Primzahlen weniger als 1000000; 78.498 wurden in 20 ms gefunden
- Finding Primzahlen weniger als 10000000; 664.579 wurden in 143 ms gefunden
- Finding Primzahlen weniger als 100000000; 5761455 wurden in 2024 ms gefunden
-
Finding Primzahlen weniger als 1000000000; 50847534 wurden in 23839 ms
gefunden//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(); }
Es führt uns unter einer Sekunde (2,4 GHz), um die ersten 150000 Primzahlen in Python mit Sieb des Eratosthenes zu erzeugen:
#!/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]))
Beispiel:
$ 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]
In 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;
}
}
Ausgabe:
Insgesamt benötigte Zeit,: 2,087 Sekunden
Unter Berücksichtigung der Tatsache, dass es bessere Möglichkeiten für Primzahlen aussehen ...
Ich denke, dass man diese Schleife nehmen:
for (int i = 2; i < top; i++)
und machen es so, dass Ihre Zählervariable i von 3 geht und versucht, nur die Mod auf ungerade Zahlen zu tun, da alle Primzahlen außer 2 sind nie durch irgendwelche geraden Zahlen teilbar ist.
Ist die erneute Deklaration der Variablen prime
while (count < topPrime) {
boolean prime = true;
innerhalb der Schleife es ineffizient machen? (Ich nehme an, es spielt keine Rolle, denn ich würde denken, Java diese optimieren würde)
boolean prime;
while (count < topPrime) {
prime = true;
C #
Erweiterung zum Aistina Code :
Dies macht sich die Tatsache zunutze, dass alle Primzahlen größer als 3 sind der Form 6n + 1 oder 6n -. 1
Dies war etwa 4-5% Geschwindigkeitserhöhung über um 1 erhöht wird jeder durch die Schleife.
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;
}
}
Meine Meinung zu Optimierung, die Vermeidung zu kryptisch Tricks. Ich benutze den Trick gegeben durch I-GIVE-TERRIBLE-Ratschläge, die ich kannte und vergessen ...: -)
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();
}
}
Ja, habe ich ein markiertes weiterhin erste Mal, dass ich versuche, sie in Java ...
Ich weiß, ich Berechnung der ersten paar Primzahlen überspringen, aber sie gut bekannt sind, keinen Sinn, sie neu zu berechnen. :-) Ich kann ihren Ausgang hart Code, wenn nötig! Neben, macht es keinen entscheidenden Vorsprung geben sowieso.
Ergebnisse:
- Erste
Last prime = 2015201
Gesamtzeit = 4,281
- Zweite
Last prime = 2015201
Gesamtzeit = 0,953
Nicht schlecht. Könnte ein wenig verbessert werden, nehme ich an, aber zu viel Optimierung kann guten Code töten.
Es sollte möglich sein, die innere Schleife doppelt so schnell zu machen, indem nur die ungeraden Zahlen zu bewerten. Nicht sicher, ob diese gültig Java ist, ich bin zu C ++ verwendet, aber ich bin sicher, dass es angepasst werden kann.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
habe ich mich entschlossen, dies zu versuchen, in F #, meinen ersten anständigen Versuch es. Unter Verwendung des Sieb des Eratosthenes auf meinem 2.2Ghz Core 2 Duo läuft es durch 2..150,000 in etwa 200 Millisekunden. Jedes Mal, es ruft sich selbst ist es die aktuellen Multiples aus der Liste eliminiert, so wird es nur schneller, wenn es entlang geht. Dies ist einer meiner ersten Versuche in F # so dass alle konstruktiven Kommentare geschätzt würde.
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
Ich wette Miller-Rabin schneller wäre. Wenn Sie genügend zusammenhängende Zahlen testen wird es deterministisch, aber ich würde nicht einmal die Mühe. Sobald ein randomisierten Algorithmus den Punkt erreicht, der seine Ausfallrate der Wahrscheinlichkeit entspricht, dass ein CPU Schluckauf ein falsches Ergebnis führen wird, spielt es keine Rolle einfach nicht mehr.
Hier ist meine Lösung ... sein ziemlich schnell ... es die Primzahlen zwischen 1 und 10 Millionen in 3 Sekunden auf meinem Rechner (Core i7 @ 2,93 GHz) auf Vista64 berechnet.
Meine Lösung ist in C, aber ich bin kein professioneller C-Programmierer. Fühlen Sie sich frei, den Algorithmus und den Code selbst zu kritisieren:)
#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;
}
Hier ist mein nehmen auf sie. Das Programm wird in writtern C und dauert 50 Millisekunden auf meinem Laptop (Core 2 Duo, 1 GB RAM). Ich halte alle berechneten Primzahlen in einem Array und versuchen Teilbarkeit nur bis sqrt der Zahl. Natürlich ist dies nicht funktioniert, wenn wir brauchen sehr große Anzahl von Primzahlen (versucht, mit 100 Millionen) als Array zu groß wächst und seg Fehler gibt.
/*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 - nicht sicher, ob dies Java-Code
Sie werden stöhnen möglicherweise , aber ich wollte Paradigma umschreiben mit ich gelernt habe, in Java zu vertrauen und sagten, dass sie etwas Spaß haben, stellen Sie sicher, dass sie verstehen, dass Spezifikation sagt nichts, was Auswirkungen auf die Bestellung zurückErgebnisMenge, auch würden Sie Ergebnismenge Punktwerte () auf einen Listentyp gegeben meine Einmal in dem Editor, bevor eine kurze Besorgung unter
gegossen=============== ungetesteten Code beginnen ===============
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 ....
}
=============== Ende ungetesteten Code ===============
Hash-Sets Verwendung ermöglicht die Suche Ergebnisse wie B-Bäume, ergibt sich somit gestapelt werden können, bis die Maschine dann zu versagen beginnt, dass Ausgangspunkt für einen weiteren Block von Tests verwendet werden könnte == das Ende eines Durchlaufs als Konstruktor Wert verwendet für einen anderen Lauf auf der Festplatte arbeiten, persistierende bereits erreicht und ermöglicht inkrementelle Feed-Forward-Designs. jetzt ausgebrannt, Schleife Logik Bedarfsanalyse.
Patch (plus hinzufügen 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
Ich habe diesen Code irgendwo auf meinem Rechner, wenn ich der Lektüre dieses Blog-Eintrag über Primzahlen gestartet. Der Code ist in C # und der Algorithmus habe ich kam aus meinem Kopf, obwohl es wahrscheinlich irgendwo auf Wikipedia ist. ;) Wie dem auch sei, kann es die ersten 150000 Primzahlen in etwa 300ms holen. Ich entdeckte, dass die Summe der ersten n ungerade Zahlen n ^ 2 gleich ist. Auch hier gibt es wahrscheinlich einen Beweis für diese irgendwo auf wikipedia. Also das weiß, kann ich einen Algorithmus schreiben, die nie eine Quadratwurzel berechnen wil haben, aber ich habe berechnen schrittweise die Primzahlen zu finden. Wenn Sie also das Nth prime wollen, wird diese algo hat die (N-1) vor Primzahlen vor zu finden! Also da ist es. Genießen Sie!
//
// 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;
}
Hier ist mein Beitrag:
Maschine: 2,4 GHz Quad-Core i7 w / 8GB RAM @ 1600MHz
Compiler: clang++ main.cpp -O3
Benchmarks:
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$
Quelle:
#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;
}
Das mit dem Sieb des Erastothenes Ansatz nutzt, habe ich es so viel optimiert, wie ich kann mit meinem Wissen. Verbesserungen begrüßen zu können.
