Primzahlen < Sonstiges < Schule < Mathe < Vorhilfe
|
Hallo,
ich soll ein Programm schreiben das schnellstmöglichst vielle Primzahlen ausrechnet in einem Bereich von a bis b (b ist ca. im Milliardenbereich).
Jetzt habe ich mich mal auf die Suche nach verschiedenen Verfahren geamacht und das Sieb des Eratosthenes gefunden. Doch mein Lehrer meint, dies sei recht langsam, es gebe etwas schnelleres. Habt ihr eine Idee?
Vielen Dank schon mal ;)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:20 Di 14.12.2004 | | Autor: | Stefan |
Hallo Superente!
Ich weiß nicht, ob das folgende das schnellste Verfahren ist, aber es ist immerhin schneller als das Sieb des Eratosthenes  :
Man kann zeigen, dass jede Primzahl $p>5$ von der Form
$p = 30 k + m$
mit
$m [mm] \in \{1,7,11,13,17,19,23,29\}$
[/mm]
ist. Also braucht man nur diese Kandidaten zu testen.
Dies kann man mit dem ![[]](/images/popup.gif) Lucas-Test oder dem Pratt-Test machen.
Aber ich bin kein Experte auf dem Gebiet und lasse die Frage daher vorerst auf "teilweise beantwortet" stehen. Du kannst es deinem Lehrer ja mal so vorschlagen.
Viele Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:18 Mi 15.12.2004 | | Autor: | Superente |
Hi,
danke für die Info. Hast du vielleciht noch weitere Dokumentationen? Ich verstehe es noch nciht ganz mit dem r und q daher würde ich gern dazu mehr lesen. In google findet man dazu leider nur 4?! Treffer.
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:33 Di 28.12.2004 | | Autor: | sascha4 |
Hallo,
die Frage ob eine gegebene Zahl eine Primzahl ist lässt sich wie folgt lösen (galt im jahr 2002 als der Effektivste Algorithmus):
Er findet sich in dem PDF http://www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Folien0405/primesinnp4.pdf auf Seite 9 und heißt AKS-Algorithmus.
Jetzt musst du "nur noch" die Kandidaten für Primzaheln (siehe Antworten anderer) damit durchtesten lassen.
Viele Grüße
Sascha
|
|
|
|
