 |
|||
| HSG |
|
Fingerübungen
Gib folgende Befehle in der Shell ein und schaue dir immer wieder die gespeicherte Liste L an.
L=[42,-5.34,'otto']
L
L[0]
L[1]
L[2]
L[3]
L[-1]
L[-2]
L[1] = 'Adam'
L
L.append('Eva')
L
L.append(17)
L
del L[2]
L
L.insert(2,'hsg')
L
L.insert(0,'hsg')
L
L.remove('hsg')
L
'hsg' in L
L.remove('hsg')
L
'hsg' in L
del[0]
del[1]
L
L = [44,55,12,42,94,6,67]
L
L.sort()
L
Beispiel 1: Sieb des Eratosthenes
# -*- coding: iso-8859-1 -*-
# Autor: mk, 2.6.08; spr, 25.2.21
from time import *
def sieb(n):
P =[] # leere Liste
for zahl in range (2,n+1):
P.append(zahl) # Liste P = [2,3,4,...,n]
i = 0 # Position der aktuellen Primzahl
p = P[i] # p ist aktuelle Primzahl
while p*p <= n: # 1)
v = 2*p # v ist ein Vielfaches von p, zuerst v=2*p
while v <= P[-1]: # ist v <= letztes Element der Liste P?
if v in P: # ist v überhaupt noch in der Liste?
P.remove(v) # v aus Liste entfernen
v = v+p # zum nächsten möglichen Vielfachen
i = i+1
p = P[i] # nächste (nicht gestrichene) Zahl in der Liste
return P
# 1) Jede nichtprime Zahl <= n muss durch eine Primzahl p teilbar sein, für
# die p*p <= n gilt. Daher muss man nur bis zu dieser Primzahl p die
# Vielfachen streichen.
# Angenommen p1<p2<..<pg sind alle die Primzahlen mit p*p <= n. Sei m <= n
# und nicht prim, dh. pgg>pg ist eine Primzahl mit pgg | m. Also gilt
# m = pgg*f. f ist eine Zahl, die nicht durch p1,...,pg teilbar ist, dh.
# f >= pgg. Damit folgt m >= pgg*pgg > n (letztes > nach Voraussetzung).
# Widerspruch zu m <= n.
if __name__ == '__main__': # wenn Modul als Hauptprogramm, dann Tests
t1 = process_time()
print sieb(1000)
t2 = process_time()
print('Rechenzeit: '+str(t2-t1)+'s')
Die zu streichenden Vielfachen könnte man auch bei v = p*p beginnen lassen. Messungen ergeben aber keine kürzeren Rechenzeiten. Vielleicht hängt das daran, dass *2 und +p leicht im Vergleich zu p*p zu rechnen ist.
Beispiel 2: Primfaktorzerlegung
# -*- coding: iso-8859-1 -*-
# Autor: Klaus Merkert, Datum: 2.6.08
def primfac(n):
F = []
while n%2 == 0:
F.append(2)
n = n/2
while n%3 == 0:
F.append(3)
n = n/3
t = 5
diff = 2
while t*t <= n:
while n%t == 0:
F.append(t)
n = n/t
t = t + diff
diff = 6 - diff
if n > 1:
F.append(n)
return F
Für eine Primzahl p > 3 gibt es nur die Fälle: 1.Fall: 3∣(p+1) oder 2.Fall: 3∤(p+1). Im 1.Fall könnte p+2 eine Primzahl sein, da ungerade und nicht durch 3 teilbar. p+4 =p+1 + 3 ist aber wieder durch 3 teilbar, sodass der nächste Primzahl-Kandidat p+6 wäre. Im zweiten Fall muss p+2 durch 3 teilbar sein, weil p und p+1 es nicht waren. Man wird daher p+4 untersuchen. p+5 ist aber wieder durch 3 teilbar, sodass p+6 es nicht ist. p+6 kommt als Primzahl-Kandidat in Frage. Im ersten Fall sollte man also p+2 und dann p+6, im zweiten Fall p+4 und dann p+6 untersuchen. Die Primzahlkandidaten haben also abwechselnd eine Differenz von 2 und 4.
Links
- Liste - wikipedia
- Listen als Stacks