Primzahltests

Mathematik Didaktik Seminar

Primzahltests

Im Zusammenhang mit der Suche nach der Produktdarstellung einer Zahl stellt sich vor allem die Frage, wie der erste Teiler zu finden ist und ob die Zahl eine Primzahl ist. Im Falle der Primalität (der Primzahleigenschaft) erübrigt sich schließlich die Suche nach Teilern.

Das Sieb des Eratosthenes

Eine - schon seit der Antike bekannte - Methode, Primzahlen zu finden wird dem griechischen Universalgelehrten Eratosthenes (ca. 275-195 v.Chr.) zugeschrieben.
Dazu stelle man sich alle natürlichen Zahlen, außer der 1, der Reihe nach hingeschrieben vor. Zuerst werden alle Zahlen mit Ausnahme der 2 selbst, gestrichen, die Vielfaches von 2 sind, also 4, 6, 8, ....
Keine von ihnen ist - als Vielfaches von 2 - eine Primzahl.
Dann streicht man alle Vielfachen der ersten nicht durchgestrichenen Zahl, hier also der "3", aber ohne diese selbst.
Die nächste nicht durchgestrichene Zahl ist die 5. Sie muss Primzahl sein, da sie keinen (kleineren) Primteiler besitzt. Nun werden die Vielfachen von 5 - außer der 5 selbst - gestrichen, also 10, 15, 20, 25, ....
Anschließend finden wir die 7 usw.

Führt man dieses Verfahren fort, bleiben alle Primzahlen bis zu einer gewissen Grenze ungestrichen.

Hier einige Illustrationen dazu:
Als HTML, Javascript, Applet, Geradenschnittpunkte

Der berühmte Mathematiker Gauß schaffte es auf diese Weise die Primzahlen bis 3 Millionen per Hand zu ermitteln, in dem er in seiner freien Zeit die eine oder andere "Chililade", ein Intervall von 1000 Zahlen, abstrich.

Das Verfahren des Primzahl-Siebens eignet sich nur für kleinere Zahlen und hatte bei der Suche nach Primzahl-Größen keinen nennenswerten Einfluss.

Direkte Teilersuche

Eine weitere Methode, Teiler einer Zahl zu finden bzw. im Falle keines Teilers die Primeigenschaft nachzuweisen beruht auf der versuchsweisen Teilung.
Im einfachsten Verfahren dieser Art würde man alle Zahlen zwischen 1 und der gegebenen Zahl nehmen und prüfen, ob der Darstellungssatz den Rest 0 liefert - also eine Probedivision durchführen.
Ruft man sich aber ins Gedächtnis, dass zu jedem Teiler ein komplementärer Teiler existiert, so sieht man, dass der grösste (echte) Teiler einer Zahl nicht grösser als deren Wurzel sein kann.
Zudem lässt sich der Teiler 2 und damit die Vielfachen von 2 leicht aus den Testkandidaten ausschliessen: Zu Beginn des Verfahrens testet man einmal die Teilbarkeit durch 2, dann fährt man mit der 3 fort und erhöht jeweils um 2, um die geraden Zahlen auszulassen.
Im Idealfall nimmt man als Testkandidaten nur die Primzahlen von 2 bis zur Wurzel der gegebenen Zahl.

Dieser Algorithmus eignet sich hervorragend zur Umsetzung im Informatikunterricht, deshalb hier ein kleines Ablaufschema:

Sei s die zu testende Zahl
Sei f=2 der erste Faktor der getestet wird
Wenn f|s dann ist s nicht prim
Andernfalls f=3
Wenn f|s dann ist s nicht prim
Andernfalls erhöhe f um 2, solange f Wurzel aus s
s ist prim

Oder im C++ (oder Javascript)-Format:

function Primzahl(Testzahl) {

s = Testzahl;

f = 2;
if (!(s%f)) return false;
else f=3;

do

{
if (!(s%f)) return false;
f = f + 2;
} while (f <= sqrt(s));

return true;

}

Bei den ersten, relativ kleinen Primzahlgrößen hat dieses Nachweisschema funktioniert. Für die wahren Zahlengiganten ist es jedoch trotz steigender Rechnergeschwindigkeiten wenig geeignet.

Der Lucas Test

Für große Zahlen ist der Lucas-Test (erstmal 1876 beschrieben) besser geeignet. Bei diesem Verfahren bildet man nach der Rekursionvorschrift x₁ = 4 und x_n+1= x_n²-2 die sogenannte Lucas-Folge: 4, 14, 194, 37634, ...
M_n ist genau dann prim, wenn M_n Teiler von x_n-1 ist.
Der Nachteil dieses Verfahrens liegt darin, dass die Testzahlen schnell viel größer werden als die zu untersuchende Zahl. Der verbesserte Lucas-Lehmer-Test betrachtet deshalb nur noch die Reste der Folgeglieder bezüglich M_n.

Weitere Primzahltests

siehe Prime Pages