Thomas-W. Meyer
Programm prim.c 25.04.2003
Allgemeines | Programmstart | Programmierung | Erweiterung | Download | Kontakt | zurück
1. Allgemeines
Das Programm ermittelt Primzahlen - natürlich, möchte man sagen. Die gefundenen Primzahlen werden in fortlaufend numerierte Dateien 'prim000000000.txt' u.s.w. geschrieben. Es ist deshalb nicht gerade schnell, kann jedoch aus unten angegebenem Grund einen recht großen Teil der natürlichen Zahlen untersuchen (wenn auch mit erheblichem Zeitaufwand und Plattenspeicher).
Die Ermittlung erfolgt zur Zeit, indem geprüft wird, ob eine gegebene Zahl durch bereits ermittelte Primzahlen teilbar ist. Ist dies nicht der Fall, bleibt also für alle bereits bekannten Primzahlen ein Rest, so muss die zu untersuchende Zahl selbst eine Primzahl sein. Die Ganzzahldivisionen können mit einer Primzahl größer der Wurzel der zu untersuchenden Zahl abgebrochen werden.
Das Programm verwendet den Datentyp 'unsigned long long' entsprechend dem C99-Standard. Kompiliert wurde es von mir mit dem GNU-Compiler gcc 2.95.3 unter Linux 2.4.10 mit KDevelop 2.0.2 und dem durch automake / autoconf / configure erzeugten Makefile. Unter Windows habe ich es mit gcc 3.2 aus dem Paket MinGW 2.0.0 kompiliert, wobei die Zeilen
#define LINUX 1 #define DAEMON 1
auskommentiert wurden. Statt eines Makefiles habe ich die Kommandos
gcc -o prim prim.c
strip prim.exe
benutzt. Mit VC 6.0 sollte es kein Problem sein, eine Projektdatei zu erzeugen. Unter Windows, gleich welcher Compiler, wird der Datentyp 'unsigned __int64', die Formatspezifikation '%I64u' und die Funktion '_atoi64()' benutzt werden. Dies ist, soweit ich weiß - zumindest unter dem von mir verwendeten Windows 98, eher von der Laufzeitumgebung MSVCRT abhängig als vom Compiler.
Der Datentyp 'unsigned long long' erlaubt Zahlenbereiche von 0 bis 1.8 * 10 ^ 19, natürlich nicht in Exponentialschreibweise. Aus Gründen der Programmierung können natürliche Zahlen bis 3.2 * 10 ^ 16 untersucht werden (siehe Kommentar zur Funktion fa() ).
Zur Untersuchung natürlicher Zahlen bis etwa zwei Milliarden braucht das Programm auf einem recht langsamen Rechner (350 MHz) etwas mehr als einen Tag und etwa 300 Megabyte Plattenspeicher (auf jedem Rechner). Es läuft auch noch auf einem 120 MHz - Rechner mit 48 MB RAM. Das Laufzeitverhalten wird sich deutlich verbessern, sobald das Verfahren auf das Sieb des Eratosthenes umgestellt ist.
In den Primzahldateien wird jeweils die erste Primzahl und dann der Abstand zum jeweiligen Vorgänger gespeichert. Die Konstante PPF definiert die Anzahl der Abstände (eine Million).
Im Anschluss an den eigentlichen Quelltext sind drei Programme zur Auswertung angehängt. Sie sollen später zur Ermittlung der Anzahl der Lücken im allgemeinen und bei Zwillingen dienen (nicht an den Datentyp 'unsigned long long' und die Maximalgröße zu untersuchender Primzahlen angepasst). Sobald diese Programme vollständig integriert sind, kann auf das Speichern verzichtet werden.
2. Programmstart
Gestartet wird im Terminal oder in der DOS-Eingabeaufforderung mit
'prim'
Unter Linux kann der Prozess mit
'prim stop'
angehalten werden. Unter DOS ist
'prim <zahl2>'
zu empfehlen, womit sich das Programm an der durch <zahl2> definierten Stelle beendet.
Falls durch Strg-C abgebrochen wird, muss die letzte Zeile der letzten Datei gelöscht werden, die
vermutlich unvollständig ist. Einfacher ist es, die letzte Datei komplett zu löschen.
Mit
'prim restart'
kann die Ermittlung fortgesetzt werden. Neu ermittelte Primzahlen werden am Ende der letzten
Datei eingetragen.
Mit
'prim restart <zahl>'
wird die Ermittlung an einer bestimmten Stelle fortgesetzt, jedoch werden die Primzahlen in eine fortlaufend numerierte Datei namens 'from000000000.txt' geschrieben, die nicht existieren darf oder ggf. überschrieben wird. Damit kann die Ermittlung auf mehrere Rechner verteilt werden.
'prim restart <zahl> <zahl2>'
schreibt ebenfalls 'from...'-Dateien und zwar ab <zahl> bis <zahl2>.
'prim -h'
gibt Hinweise zu den Startoptionen aus.
3. Programmierung
Nach den einleitenden Kommentaren folgen einige vom Betriebssystem abhängige Definitionen.
Wichtig ist die Variable 'ip' und das Feld 'a'. In 'a' werden die ersten zehn Millionen Primzahlen gespeichert, um die Ganzzahldivisionen durchzuführen. 'ip' ist der Zähler dafür.
Unter Linux läuft das Programm als Hintergrundprozess, als sogenannter Dämon. 'main' startet den Hintergrundprozess und 'sig_term' beendet ihn bei Empfang des Signals SIGTERM, das durch 'prim stop' ausgelöst wird.
Die Primzahlermittlung erfolgt in 'child_main()'. Die do-while - Schleife läuft bis zum definierten Ende oder bis alle Zahlen überprüft sind, die durch das a - Feld behandelt werden können. Mit zehn Millionen Primzahlen (NUM) würde das Programm praktisch endlos lange laufen. NUM kann jedoch auch verringert werden. Ist die zu untersuchende Zahl eine Primzahl wird die Differenz zu ihrem Vorgänger in die geöffnete Datei geschrieben und anschließend in der Vorgängervariable 'v' gespeichert. Falls die Anzahl der ermittelten Primzahlen das Limit PPF überschreitet, wird die Datei geschlossen, eine neue geöffnet und die letzte Primzahl geschrieben. Zum Schluß wird die zu untersuchende Zahl um zwei erhöht - es werden nur ungerade Zahlen geprüft. Falls das Programm alle zu ermittelnden Zahlen überprüft hat, wird die letzte Datei geschlossen.
Die folgenden beiden Funktionen geben Hinweise bzw. Fehlermeldungen aus.
'analyseargs()' wertet die Kommandozeilenargumente aus. 'restart' ist nur möglich, wenn mindestens eine Primzahldatei existiert.
In 'getlatestthings()' werden beim Start die wichtigsten Variablen gesetzt. Erfolgt der Start mit 'prim' ohne Argumente, ist die erste zu untersuchende Zahl die 3, der erste Vorgänger wird ohne Prüfung mit 2 angenommen. Beim Start per 'prim restart' oder 'prim restart <zahl>' werden zunächst bereits vorhandene Dateien 'prim000000000.txt' gelesen und auf das Feld 'a' gespeichert. Diese Dateien müssen nicht komplett zehn Millionen Zahlen enthalten - das Feld 'a' würde unter Umständen vervollständigt werden.
Wurde auf der Kommandozeile nach 'restart' noch eine Zahl angegeben, speichert das Programm gefundene Primzahlen in 'from....txt'-Dateien mit Null beginnend. Sollte also schon einmal ein Start des Programms mit 'restart <zahl>' erfolgt sein, müssen vor einem Neustart gespeicherte Dateien gesichert werden. Der erste Eintrag ist die nächstgrößere Primzahl. Die angegebene Zahl ist selbst wahrscheinlich selten eine Primzahl. Dann ist die Lückengröße des ersten Eintrags natürlich falsch. Ein Programm zum Abgleich der 'from...'- mit den 'prim...' - Dateien müßte dies berücksichtigen.
Erfolgt der Start mit 'prim restart' ohne Zahl wird die Datei mit der höchsten Nummer gesucht, bis zur letzten Zeile gelesen und diese Zahl als Vorgängerprimzahl gesetzt.
Anschließend werden noch die Fälle "es existiert eine Datei ohne Einträge" und "die letzte Datei enthält eine Million Einträge" geprüft und entsprechende Dateien geöffnet. Die Ermittlung wird mit der nächsten ungeraden Zahl größer als der gesetzte Vorgänger begonnen.
In 'isprime' erfolgt die Überprüfung einer gegebenen Zahl und liefert 'wahr' oder 'falsch' zurück, je nachdem, ob es eine Primzahl ist oder nicht. Der Aufruf von 'signal()' ist nur unter Linux von Bedeutung. Anschließend wird der Zähler 'ip' um eins erhöht und die gefundene Primzahl auf das Feld 'a' gespeichert, falls es noch nicht gefüllt sein sollte.
Die Funktion 'fa()' ist mit '#if NECESSARY' auskommentiert und nicht ausprogrammiert. Sie soll wie das a - Feld bereits ermittelte Primzahlen liefern, jedoch größere. Interessant wird diese Funktion erst, wenn der Datentyp 'unsigned long long' durch 'mpz_t' ersetzt würde. Dies ist ein Integer-Datentyp aus der GNU Multiple Precision Library, einer Bibliothek zur hochgenauen Arithmetik mit unbeschränktem Zahlenbereich. Durch den Start mit 'prim restart <zahl>' ergäbe sich die Möglichkeit, Bereiche weit oberhalb von 1.8 * 10 ^ 19 zu untersuchen.
Mit '#if CONVERT' auskommentiert ist ein Programm zum Konvertieren von Dateien im 0.90'er Format in das augenblickliche Format. Dieser Teil sollte in eine zweite Quelltextdatei kopiert und für sich kompiliert werden.
Der Rest ist per Compilerschalter auskommentiert und noch nicht ausprogrammiert. 'gap' liest aus den Primzahldateien die Lückengröße und speichert deren jeweilige Anzahl in der Datei 'gap.txt'.
'twin' liest ebenfalls die Primzahldateien und speichert alle Zwillinge wie 41 43 oder 59 61 und auch ihre jeweilige Lückengröße in der Datei 'twin.txt'.
Das letzte Programm 'twingap' bildet aus 'twin.txt' die Anzahl der jeweiligen Lücken von Zwillingen und speichert sie in 'twingap.txt': auch bei nur fünfzig Millionen ermittelten Primzahlen, etwa bei zwei Milliarden, sind deutlich herausragend 30 und 210 als häufige Lückengrößen zu erkennen, was Odlyzko und Kollegen wohl zu ihrer "Jumping Champions Conjecture" geführt hat.
4. Erweiterung
Ich habe dem Programm die Versionsnummer 0.91 gegeben, weil nicht alles völlig ausprogrammiert ist und insbesondere das Sieb integriert und die Auswertungsprogramme erweitert werden könnten. Im Quelltext unter TODO stehen weitere Punkte. Ich bin für alle Vorschläge offen.
5. Download
6. Kontakt
Bei Fragen, Anregungen, Vorschlägen, Kritiken und Bug-Reports schicken Sie bitte an Thomas-W. Meyer eine E-Mail (thowmeyer@gmx.net)