Primzahlen, Primzahlen, Primzahlen...
Verfasst: Donnerstag 25. Oktober 2012, 18:05
Hey zusammen,
ich hab einfach zum Spass mal versucht, mit Python die Primzahlen errechnen zu lassen von 2 bis zu einer Grenze [bis]. Erst heb ich einfach jedes Element der Liste auf "Primheit" überprüft - nicht sehr effizient das Ganze... dann hab ich angefangen, Regeln einzubauen, die das Ganze schneller machen.
Irgendwann bin ich dann auf Sieb des Eratosthenes (oder so) gestossen und hab dies versucht, umzusetzen - mit Erfolg eigentlich, das hat so ausgeschaut:
das klappt! 1229 Primzahlen bis 10000 - müsste stimmen laut Inter-Njet. Heute habe ich mich mit einem Kollegen unterhalten bei der Arbeit und dieser hatte noch etwas eingeworfen: Eigentlich müsste es ja ausreichen, jeweils die Vielfachen bis und mit 9 aus der Liste zu streichen; schon dann müssten doch die Primzahlen übrig bleiben..? Ich hatte mir dies überlegt, hin und her, und kam zum Schluss - doch, das müsste doch stimmen..? Dann hab ich das probiert:
Leute, das stimmt nicht... es gibt dann plötzlich 2288 Primzahlen bis 10000. Ich bin nicht völlig auf dem Holzweg denk ich, aber da fehlt was. Ich habe mir nun überlegt: 11 x 11 z.Bsp. gibt 121 - da denk ich liegt der springende Punkt! Demnach müsste ich die Vielfachen anders rechnen, also mit den übrigbleibenden Zahlen mal rechnen..? Also mit 11 wär's 11 x 13, 11 x 17, 11 x 19 etc..?
Geht Ihr mit mir einig oder seht ihr noch weitere Punkte / andere Ansätze..?
Cheers!
ich hab einfach zum Spass mal versucht, mit Python die Primzahlen errechnen zu lassen von 2 bis zu einer Grenze [bis]. Erst heb ich einfach jedes Element der Liste auf "Primheit" überprüft - nicht sehr effizient das Ganze... dann hab ich angefangen, Regeln einzubauen, die das Ganze schneller machen.
Irgendwann bin ich dann auf Sieb des Eratosthenes (oder so) gestossen und hab dies versucht, umzusetzen - mit Erfolg eigentlich, das hat so ausgeschaut:
Code: Alles auswählen
# -*- coding: cp1252 -*-
import time
def primzahlen(bis):
"""Gibt die Primzahlen von 1 bis [bis] zurück"""
alle = range(2, bis + 1)
for zahl in alle:
if zahl > (bis / 2):
break
f_min = 2
f_max = bis / zahl
for f_x in range(f_min, f_max + 1):
vielfaches = zahl * f_x
if vielfaches in alle:
alle.remove(vielfaches)
return alle
t_a = time.clock()
ni = primzahlen(10000)
t_b = time.clock()
t_passed = t_b - t_a
print ni
print len(ni)
print t_passedCode: Alles auswählen
# -*- coding: cp1252 -*-
import time
def primzahlen(bis):
"""Gibt die Primzahlen von 1 bis [bis] zurück"""
alle = range(2, bis + 1)
for zahl in alle:
if zahl > 9:
break
f_min = 2
f_max = bis / zahl
for f_x in range(f_min, f_max + 1):
vielfaches = zahl * f_x
if vielfaches in alle:
alle.remove(vielfaches)
return alle
t_a = time.clock()
ni = primzahlen(10000)
t_b = time.clock()
t_passed = t_b - t_a
print ni
print len(ni)
print t_passedGeht Ihr mit mir einig oder seht ihr noch weitere Punkte / andere Ansätze..?
Cheers!
thx Dude