Primzahlen effizient berechnen
Verfasst: Mi Sep 16, 2009 8:11 pm
Tag 
(Seit wann haben wir ein Mathe-Forum?^^)
Was ich mich frage: Wie berechne ich Primzahlen möglichst effizient?
Im Moment mache ich das folgendermaßen:
Ich überprüfe alle Zahlen von 2 bis sqrt(Zahl), ob sie ein Teiler von Zahl sind.
Finde ich einen Teiler, dann ist Zahl keine Primzahl.
Das Ganze nun in eine for-Schleife gepackt, Start- und Endwerte mitgeben und durchlaufen lassen.
Funktioniert, ist aber doch schon recht aufwendig bei größeren Zahlen.
Was ich jetzt auch noch so für möglich halte ist folgendes:
Es werden alle Primzahlen von 2 aufwärts in einen Vector gespeichert. Somit muss eine Zahl nur daraufhin getestet werden, ob sie durch eine der (schon bekannten) Primzahlen teilbar ist.
Wenn ja, dann ist es keine Primzahl (da es ja dann ein Vielfaches einer anderen Primzahl ist). Ansonsten kommt die Zahl in den Vector mit rein. Die Zahl+1 braucht dann nicht einmal überprüft werden, da die dann durch 2 teilbar ist (mal von der Primzahl 2 abgesehen). Das Spielchen so lange, bis man eine Zahl größer als dem Startwert gefunden hat oder bis die Zahl größer wird, als der Endwert.
Fällt euch noch etwas schnelleres ein?
(Seit wann haben wir ein Mathe-Forum?^^)
Was ich mich frage: Wie berechne ich Primzahlen möglichst effizient?
Im Moment mache ich das folgendermaßen:
Ich überprüfe alle Zahlen von 2 bis sqrt(Zahl), ob sie ein Teiler von Zahl sind.
Finde ich einen Teiler, dann ist Zahl keine Primzahl.
Das Ganze nun in eine for-Schleife gepackt, Start- und Endwerte mitgeben und durchlaufen lassen.
Funktioniert, ist aber doch schon recht aufwendig bei größeren Zahlen.
Was ich jetzt auch noch so für möglich halte ist folgendes:
Es werden alle Primzahlen von 2 aufwärts in einen Vector gespeichert. Somit muss eine Zahl nur daraufhin getestet werden, ob sie durch eine der (schon bekannten) Primzahlen teilbar ist.
Wenn ja, dann ist es keine Primzahl (da es ja dann ein Vielfaches einer anderen Primzahl ist). Ansonsten kommt die Zahl in den Vector mit rein. Die Zahl+1 braucht dann nicht einmal überprüft werden, da die dann durch 2 teilbar ist (mal von der Primzahl 2 abgesehen). Das Spielchen so lange, bis man eine Zahl größer als dem Startwert gefunden hat oder bis die Zahl größer wird, als der Endwert.
Fällt euch noch etwas schnelleres ein?