Primzahlen berechnen, ist ja ein beliebtes Programmierthema bei Lehrern.
Ich mußte das nie machen und hab' mir auch nicht viele Lösungen angesehen.
Vielleicht ging mir gerade deshalb manchmal diese Idee im Kopf rum. Also:
Wenn man ohne Rechner wissen will, ob eine Zahl eine Primzahl ist, prüft man wohl zuerst, ob sie durch 2 oder durch 3 teilbar ist.
Wenn das nicht der Fall ist, kann es aber noch größere Teiler geben.
Mein Gedanke, den bestimmt schon viele andere hatten, war, daß auch diese Teiler nicht beliebig groß sein können. Mit jeder Prüfung verringert sich sogar ihre mögliche Größe. Beispiel:
1. Prüfung: 17 ist nicht durch 2 teilbar. 9 * 2 wären schon 18. Die Teiler, die man noch prüfen müßte, müßten also kleiner als 9 sein.
2. Prüfung: 17 ist nicht durch 3 teilbar. 6 * 3 wären schon 18. Die Teiler, die man noch prüfen müßte, müßten also kleiner als 6 sein.
Usw.
Wenn man ein Primzahl prüft, erreicht die mögliche Größe der Teiler irgendwann die schon geprüften Teiler. Dann braucht man nicht mehr weiter zu prüfen (und weiß, daß es eine Primzahl ist).
Hab' das grad' mal versucht, in Code umzusetzen:
Code: Alles auswählen
#!/usr/bin/env python
# coding: iso-8859-1
def isPrim(num):
""" Not sure, if this works correctly. """
uplim = num
count = 2.
while count < uplim:
if not (num % count):
return False
uplim = num // count + 1
count += 1.
return True
for i in range(3, 201, 1):
if isPrim(float(i)):
print i
So, jetzt ist es ausnahmsweise mal willkommen, wenn ihr gründlich darüber ablästert. Ist das vielleicht der gängige Ansatz (Rad nochmal erfunden)? Oder ist das falsch, d.h. es funktioniert irgendwann nicht oder man kann es noch viel besser schreiben?
Viel Spaß