Mittwoch, 7. Oktober 2009

 

Primzahlensieb nach Eratosthenes

Schreiben Sie ein python Programm, welches für eingegebene Zahlen prüft, ob es eine Primzahl ist.
Verwenden Sie für die Primzahlbestimmung das Sieb des Eratosthenes .

Variante 1 (einfacher)

Das Programm soll eine Primzahlentabelle fixer Größe (z.B. 1000) erstellen und dann bis EOF Zahlen einlesen und ausgeben, ob die Zahl eine Primzahl ist (oder nicht).

Variante 2 (schwieriger)

Das Programm soll zunächst wieder eine fixe Tabelle erzeugen. In der Prüfphase (Eingabe der Zahlen) soll wie oben ermittelt werden, ob die Zahl eine Primzahl ist. Ist die eingegebene Zahl jedoch größer als das letzte Tabellenelement, so soll die Tabelle entsprechend erweitert und neu geprüft werden.



Lösung Variante 1


Wir müssen zunächst eine Tabelle erzeugen, die lauter True (für "eine Primzahl") enthält.

def gentable(end):
"""
erzeuge Tabelle bis Obergrenze end
end: Obergrenze
"""
tab = []
for i in range (0, end):
tab.append(True)
return tab

Die Tabelle wird als (leere) Liste implementiert, an die in einer Schleife immer True angehängt wird. Der Aufruf gentable(10) erzeugt folgende Liste: [True, True, True, True, True, True, True, True, True, True]

Eine ganze Zahl kann mit input() eingelesen werden. Tippt man aber einen Text, so interpretiert input() diesen Text als Python-Programm, d.h. im allgemeinen bekommt man folgende Fehlermeldung:

>>> input()
hallo
Traceback (most recent call last):
File "", line 1, in
File "", line 1, in
NameError: name 'hallo' is not defined
>>>
Gibt man "sinnvollen Python-Code" ein, wird dieser interpretiert:
>>> input()
float(2)/3
0.66666666666666663
>>>
Daher ist es sinnvoll, eine Eingabefunktion zu definieren:
def liesInt():
"""
lies eine ganze Zahl
"""
ok = False
while not ok:
try:
z = int(input("ganze Zahl: "))
ok = True
except EOFError:
return -1
except:
pass
return z
Diese Funktion verwendet input() und versucht die Eingabe mit int() in eine ganze Zahl umzuwandeln. Schlägt dies fehl, wird ein Laufzeitfehler (Exception) ausgelöst, der mit except: behandelt wird (bei Ende der Eingabe EOF wird ein EOFError ausgelöst (und die Funktion liefert den Wert -1). pass ist eine "Leeranweisung", die "nichts tut", d.h. bewirkt, dass Python anschließend mit der nächsten Anweisung fortsetzt.

Die Funktion sieb(tab) wendet den Algorithmus des Primzahlensiebs an, d.h. alle Vielfachen einer bereits ermittelten Primzahl werden gestrichen (False). Der Index in die Tabelle entspricht der entsprechenden Zahl:

def sieb(tab):
"""
wende Sieb des Eratosthenes auf Tabelle an
tab: Tabelle
"""
end = len(tab)
print "Sieb bis %d" % end
tab[0] = False
tab[1] = False
zahl = 2
while zahl < end:
if tab[zahl]:
for t in range(zahl + zahl, end, zahl):
tab[t] = False
zahl += 1

Es fehlt also nur noch das "Hauptprogramm":

# Hauptprogram
tab = gentable(1000)
sieb(tab)
z = liesInt()
while z > -1:
if tab[z]:
print "%d ist prim" % z
else:
print "%d ist NICHT prim" % z
z = liesInt()
Dieses erzeugt eine Tabelle mit 1000 Einträgen, ermittelt die Primzahlen. Dann werden Zahlen eingelesen und eine "Abfrage" in der Tabelle ermittelt, ob die Zahl eine Primzahl ist (if tab[z]:). Es können beliebig viele Zahlen geprüft werden (ist ja nur mehr ein Tabellenzugriff).

Hier noch einmal das ganze Programm:

#!/usr/bin/python
# -"- coding: utf8 -*-
# eratosthenesfix.py
# Primzahlenprüfung nach dem Sieb des Eratosthenes.
# 2009-10-07, Harald R. Haberstroh

def gentable(end):
"""
erzeuge Tabelle bis Obergrenze end
end: Obergrenze
"""
tab = []
for i in range (0, end):
tab.append(True)
return tab

def sieb(tab):
"""
wende Sieb des Eratosthenes auf Tabelle an
tab: Tabelle
"""
end = len(tab)
print "Sieb bis %d" % end
tab[0] = False
tab[1] = False
zahl = 2
while zahl < end:
if tab[zahl]:
for t in range(zahl + zahl, end, zahl):
tab[t] = False
zahl += 1

def liesInt():
"""
lies eine ganze Zahl
"""
ok = False
while not ok:
try:
z = int(input("ganze Zahl: "))
ok = True
except EOFError:
return -1
except:
pass
return z

# Hauptprogram
tab = gentable(1000)
sieb(tab)
z = liesInt()
while z > -1:
if tab[z]:
print "%d ist prim" % z
else:
print "%d ist NICHT prim" % z
z = liesInt()



Lösung Variante 2


Hier wird bei Bedarf die Tabelle erweitert. Ohne weitere Erklärung:

#!/usr/bin/python
# -"- coding: utf8 -*-
# eratosthenes.py
# Primzahlenprüfung nach dem Sieb des Eratosthenes.
# 2007-09-27, Harald R. Haberstroh

def gentable(tab, end):
"""
erzeuge/ändere Tabelle bis Obergrenze end
tab: (leere) Tabelle
end: Obergrenze
"""
for i in range (len(tab), end):
tab.append(True)

def sieb(tab, start):
"""
wende Sieb des Eratosthenes auf Tabelle an
tab: Tabelle
start: ab hier neu belegen
"""
end = len(tab)
print "Sieb bis %d" % end
tab[0] = False
tab[1] = False
zahl = 2
while zahl < end:
if tab[zahl]:
for t in range(zahl + zahl, end, zahl):
tab[t] = False
zahl += 1

def liesInt():
"""
lies eine ganze Zahl
"""
ok = False
while not ok:
try:
z = int(input("ganze Zahl: "))
ok = True
except EOFError:
return -1
except:
pass
return z

# Hauptprogram
tab = []
gentable(tab, 1000)
sieb(tab, 2)
z = liesInt()
while z > -1:
if z >= len(tab): # größer machen
l = len(tab)-1
gentable(tab, z * 2)
sieb(tab, l)
if tab[z]:
print "%d ist prim" % z
else:
print "%d ist NICHT prim" % z
z = liesInt()

Labels: , , ,


Kommentare:

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

This page is powered by Blogger. Isn't yours?

Abonnieren Posts [Atom]