Primzahlsuche in C++ (optimierbar?)

[Nick]

Hallo,
ich habe ein Programm zur Suche von Primzahlen in C++ geschrieben,
für die Suche in 1-10.000.000 braucht das Programm 26sek, bei 1-100.000.000
11min, bei 1-200.000.000 30min (und 45mb ramverbrauch). zwar finde ich das
programm shcon unglaublich schnell, allerdings möchte ich das weiter optimieren,
momentan mache ich einen test mit den zahlen von 1 bis 1 milliarde.
code:

#include<vector>  
#include<iostream>  
int main() {  
 std::vector<unsigned int> primes;  
 primes.push_back(2);primes.push_back(3);primes.push_back(5);  
 std::cout << "2\n3\n5\n";  
 unsigned int i = 7;  
 unsigned int j;  
 unsigned int lengthofprimesarray = 3;  
 bool isprime;  
 while(i < 1000000000) {  
  j = 1;  
  isprime = true;  
  while(j < lengthofprimesarray and !(primes.at(j)*primes.at(j) > i)) {  
   if(i%primes.at(j) == 0) {  
    isprime = false;  
    break;  
   }  
   j++;  
  }  
  if(isprime == true) {  
   primes.push_back(i);  
   lengthofprimesarray++;  
   std::cout << i << "\n";  
  }  
  if(i%10 == 3) {  
   i += 4;  
  } else {  
   i += 2;  
  }  
 }  
 return 0;  
}

geht das auch effektiver?
(btw. falls jemand den code unsauber findet: das war mein erstes brauchbares programm in c++...)

Nick

[MudGuard]

Hi,

while(j < lengthofprimesarray and !(primes.at(j)*primes.at(j) > i)) {

Du berechnest hier jedes Mal das Quadrat, um es mit i zu vergleichen.
i ändert sich in der Schleife nicht, nur j.
Es könnte also günstiger sein, einmal vor der Schleife die Wurzel aus i (und davon dann floor, um den Integer zu bekommen) zu berechnen, um dann primes.at(j) mit dieser Wurzel zu vergleichen.

cu,
Andreas

[Nick]

danke!
bei einem versuch mit dem bereich 1-10.000.000 wurde das script um 10 sekunden schneller.
allerdings habe ich ceil anstatt von floor verwendet; ist das nicht (in diesem Fall) besser?

Nick

[MudGuard]

Hi,

danke!
bei einem versuch mit dem bereich 1-10.000.000 wurde das script um 10 sekunden schneller.
allerdings habe ich ceil anstatt von floor verwendet; ist das nicht (in diesem Fall) besser?

(im folgenden gehe ich davon aus, daß i positiv ist ...)

Sei s = sqrt(i) (also Quadratwurzel von i)
Sei f = floor(s) und c = ceil(s)

Jetzt gilt: f <= s <= c.

Ist s eine Ganzzahl, ist f = s = c, es ist also egal, ob f oder c benutzt wird.

Ist s keine Ganzzahl, ist f kleiner als s und c größer als s, und c = f + 1.
Es gilt also: f < s < c bzw. f² < s² < c² bzw. f² < i < c²
c² ist bereits größer als i, also ist auch c*x > i für x >= c.
Damit c*x = i sein könnte (also Teilbarkeit existiert), muß x also kleiner als c sein.
(mit anderen Worten: es muß einen Teiler geben, der kleiner als c ist).

Das größtmögliche x, welches kleiner als c ist, ist f.
Also reicht es vollkommen, bis (einschließlich) f zu probieren, also bis floor(sqrt(i)).

cu,
Andreas

[Nick]

ups, ich hätte es sehen müssen, schande sei über mich.
danke für die recht lange antwort, wollte dir keine unnötige mühe machen...

[Christian Seiler]

Hallo,

ich habe ein Programm zur Suche von Primzahlen in C++ geschrieben,
für die Suche in 1-10.000.000 braucht das Programm 26sek, bei 1-100.000.000

http://en.literateprograms.org/Sieve_of_Eratosthenes_(C_Plus_Plus)

Viele Grüße,
Christian

[Nick]

so, die suche aller primzahlen zwischen 1 und 1 Milliarde ist fertig,
4 stunden und 18 minuten hat's gedauert. insgesamt sind es 50847534 zahlen.
kann man das nicht noch irgendwie auf 1 stunde verkürzen?

[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

[bleicher]

Grüße,
gabs nicht allerlei einfachere algorithmen zur bestimmung der primazahlen? kleine ferma & co?
MFG
bleicher

[Der Martin]

Hallo,

gabs nicht allerlei einfachere algorithmen zur bestimmung der primazahlen?

mir fällt spontan nur das Sieb des Erathostenes ein, das Christian schon erwähnt.

kleine ferma & co?

Was soll das sein?

Schönen Abend noch,
 Martin

[MudGuard]

Hi,

mir fällt spontan nur das Sieb des Erathostenes ein, das Christian schon erwähnt.

Wobei man hier natürlich Rechenzeit durch Speicherplatz ersetzt, man braucht halt Platz in der Größenordnung n/2 Bits, wenn man die Primzahlen bis n sucht (die geraden Zahlen braucht man nicht, da die 2 die einzige gerade Primzahl ist und als Ausnahme sonderbehandelt werden kann).

cu,
Andreas

[Nick]

mir fällt spontan nur das Sieb des Erathostenes ein,

ist das nciht ein wenig zu langsam bei zahlen mit mehr als 8 stellen?
naja, selbst wenn nicht, mir ging es ursprünglich um das was ich mir da
in einer langweiligen mathestunde ausgedacht hatte..

[Daniel Thoma]

Hallo Martin,

Was soll das sein?

Es gibt jede Menge Primzahltests.
Die meisten liefern allerdings in seltenen Fällen ein falsches, positives Ergebnis, erkennen also eine Zahl als Primzahl, die keine ist.
Für Verschlüsselung u.ä. nimmt man idr. solche Tests, wenn man es aber wirklich genau wissen will, kann man wenigstens einen solchen Test zuerst ausführen, bevor man alle anderen Zahlen durchprobiert.

Grüße

Daniel