Programmieren mit Harald R. Haberstroh

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: Aufgabe, Lösung, PR2, Python