Primzahlen und Primfaktoren

Im folgenden Beispiel soll ein Primteiler der Zahl 10117 berechnet werden. Es seien nur die Primzahlen < 49 = 7² bekannt. Diese Primzahlen seien in einer Datei "FileP1.txt" gespeichert. Die Reste bzw. Komplemente der Primzahlen 2, 3, 5 und 7 bei 49 werden berechnet. Ich habe ein Komplement definiert als comp_i = p_i − rest_i, d. h. dass z. B. für die Zahl 49 und p_i = 5 ist 49 mod 5 = 4 und das nächste Vielfache von 5 ist 50. Hier ist also das Komplement = 1. Die Komplemente bei 49 für die Primzahlen 2, 3, 5 und 7 sind 1, 2, 1 und 7. Die nächste Primzahl ist 11 und sein Quadrat ist 121. Die Differenz 121 - 49 = 72 und deshalb hat ein Füll-Bereich, der für diese Elemente angelegt wird, 73 Elemente. Die geraden Zahlen werden ignoriert. Deshalb wird nur das 1., 3., 5.,  . . . des Füllbereichs berechnet. Dieser Füll-Bereich wird zunächst geleert, d.h. alle diese Elemente werden auf Null gesetzt. Die 3 hat das Komplement 2 und belegt die Felder 3, 6, 9, . . . , die 5 hat das Komplement 1 und belegt die Felder 2, 7, 12, . . . Entsprechend belegt die 7 die Felder 8, 15, 22, . . . . Nachdem alle Felder belegt sind, wird der Vollständigkeit halber noch das erste Element mit 7 und das letzte Element mit 11 belegt. Nun wird mit der Auswertung des Füll-Bereichs begonnen. Alle Felder, die nicht belegt wurden, entsprechen den Primzahlen im Bereich 49 bis 121. Sie werden in einer Datei "FileP2.txt" gespeichert. Die Komplemente bei 73 (im Füllbereich) bzw. 121 werden errechnet. Sie erhält man folgendermaßen: Wird beim Befüllen die Obergrenze 73 duch ein Vielfaches einer Primzahl überschritten, dann ergibt sich das Komplement aus der Differenz dieser Zahl - 73. Mit diesen Komplementen wird im folgenden Füll-Bereich gestartet.

Dazu wird die nächste Primzahl aus "FileP1.txt"gelesen. Es ist die 13. Dieser Füllbereich soll die Elemente von 121 bis 169 = 13² aufnehmen. Er hat also 49 Elemente. Die Elemente des Füll-Bereichs werden auf Null gesetzt und dann mit Hilfe der bei 121 berechneten Komplemente wird der neue Füll-Bereich aufgefüllt. Zu den Komplementen der Zahlen 3, 5, 7 kommt jetzt die 11 dazu. Sie hat bei 121 das Komplement 11 (bzw.0). Wiederum ergeben sich die Primzahlen aus den Elementen, die nicht belegt wurden. In der Datei "FileP2.txt" kommen diese Primzahlen hinzu.

Diese Prozedur wird fortgesetzt - zunächst bis alle Primzahlen aus "FileP1.txt" aufgebraucht sind. Abbildung 1 zeigt die Quadrate der Primzahlen und die zugehörigen Komplemente bis 47², also bis 2209. Pro Zeile die Quadrate der Primzahlen und die Komplemente der Primzahlen an diesen Quadraten aufgelistet. Jetzt wird "FileP1.txt" um die Werte aus "FileP2.txt" ergänzt.Danach wird die Datei "FileP2.txt" gelöscht und mit den neuen Primzahlen gefüllt, die mit der Fortsetzung der Prozedur ermittelt werden.

Die Tabelle 1 listet die Komplemente der Primzahlen bei den Quadraten der Primzahlen. Das Quadrat 169 ist kleiner als die gesuchte Zahl 10177, die in Primteiler zerlegt werden soll. Deshalb wird der nächste Füll-Bereich berechnet. Er wird zunächst geleert und mit Hilfe der Komplemente mit den Primzahlen gefüllt. Die sich ergebenden Primzahlen werden zu den in der Datei "FileP2.txt" vorhandenen Primzahlen hinzugefügt. Man fährt mit dieser Methode fort, bis alle Primzahlen aus "FileP1.txt" bearbeitet sind. Dies ist mit mit der Primzahl 47 der Fall. Damit sind in Datei "FileP2.txt" die Primzahlen ab 53 bis 2207, der größten Primzahl kleiner 47² gespeichert.

Fährt man in dieser Weise fort, erreicht man schließlich den Zahlenbereich, in welchem p_i² ≤ 10117 ≤ p_i+1² ist. Dies ist der Bereich zwischen 97² und 101². Hier wird der Füll-Bereich gründlicher ausgewertet. Das Ergebnis ist in Tabelle 2 dargestellt. Jedem Element aus dem Füll-Bereich entspricht eine Zahl zwischen p_i² und p_i+1².

Es sind nur die ungraden Zahlen aufgelistet. Unter "Index" wird dabei der Index aus dem Füll-Bereich angezeigt. Unter "Zahl" wird die jeweilige Zahl zwischen den Primzahlquadraten aufgelistet und mit "Prim Faktor" ist ein Primfaktor angezeigt. Es ist jeweils der kleinste Primfaktor der entsprechenden Zahl. Man sieht: 10117 hat den Primfaktor 67. Mit einer kleinen Änderung im Algorithmus kann auch der größte Primfaktor < p_i+1 (hier < 101) oder alle Primfaktoren < 101 angezeigt werden. Jeder Faktor ist dann nur einmal aufgelistet. Man hat mit diesem Algorithmus auch die Primzahlen bis 10201 gefunden. Das Primzahlquadrat und die Komplemente beim Primzahlquadrat 10201 werden in einer Datei gespeichert. Dies hat den Vorteil, dass man damit bei der Suche nach einem Primteiler einer größeren Zahl auf diese Werte zurückgreifen kann und nicht wieder bei 49 beginnen muss. Man kann die Speicherung natürlich an beliebiger Stelle (am besten bei einem Quadrat einer Primzahl) vornehmen.