Primzahlsuche in C++ (optimierbar?)

[Daniel Thoma]

Hallo Nick,

Ich hab mal noch ein altes Java-Programm von mir ausgekraben, das es in 15 Minuten schafft. (Auf einem Athlon 64 3000, also schon etwas älter). Wenn Dein Rechner nicht deutlich langsamer ist, solltest Du wohl einfach mal eine schellere Programmiersprache nehmen... ;-)

insgesamt sind es 50847534 zahlen.

Das hab ich auch raus.

Das Programm implementiert das Sieb des Eratosthenes, was wohl der eigentliche Grund ist, weshalb es schneller ist. Dafür braucht es auch etwas über 100MB Speicher. Für so kleine Zahlen dürfte es auch kein sinnvolles, alternatives Verfahren geben.

Eine spontane Idee das noch zu verbessern, wäre, dass sich die Bit-Muster der verwedeten Longs ja nach gewisser Zeit wiederholen.
Also für 2 sind alle Logns gleich, für 3 wiederholt es sich nach 3, für 5 dann nach 3*5=15 usw. Dadurch kann man vermutlich das Markieren für kleine Zahlen ziemlich beschleunigen. Und gerade für die kleinen Zahlen geht ziemlich viel Zeit drauf, da für diese die meisten Markierungen gesetzt werden müssen.

  
public static void main(String[] argv) {  
    calculatePrimes(1000000000);  
}  
  
private static void calculatePrimes(int size) {  
    long[] sieve = new long[size / 64 + 1];  
    int prime = 2;  
    int count = 0;  
    calculation: while (true) {  
        System.out.println(prime);  
        count++;  
        // Mark all multiples of the current prime (except the prime its self).  
        for (int i = 2 * prime - 2; i < size - 1; i += prime) {  
            sieve[i / 64] |= (1L << (i % 64));  
        }  
        // Search for the next prime.  
        for (int i = prime - 1; i < size - 1; i++) {  
            if ((sieve[i / 64] & (1L << (i % 64))) == 0) {  
                prime = i + 2;  
                continue calculation;  
            }  
        }  
        break;  
    }  
}  

Grüße

Daniel