Python :: Aufgabe #68
2 Lösungen
Giuga-Zahlen berechnen
Anfänger - Python
von Gustl
- 13.02.2015 um 12:42 Uhr
Eine natürliche Zahl n ist eine Giuga-Zahl, wenn alle ihre Primteiler p den Wert n/p - 1 teilen.
Schreibe ein Programm welches alle Giuga-Zahlen bis zu einer festen Obergrenze ausgibt.
Erläuterung zu einer Giuga-Zahl findest du hier: Wikipedia
Schreibe ein Programm welches alle Giuga-Zahlen bis zu einer festen Obergrenze ausgibt.
Erläuterung zu einer Giuga-Zahl findest du hier: Wikipedia
Lösungen:
Python-Code
import math
primzahlen = []
def prim(zahl):
if zahl == 2:
return True
elif zahl == 0 or zahl ==1 or zahl % 2 == 0:
return False
else:
for i in range(3,int(math.sqrt(zahl))+1):
if zahl % i == 0:
return False
return True
def primfaktorzerlegung(zahl):
liste_2 = []
if len(primzahlen) == 0:
for i in range(int(grenze/2)+1):
if prim(i) == True:
primzahlen.append(i)
for j in primzahlen:
if zahl != 1:
while zahl % j == 0:
liste_2.append(j)
zahl /= j
return liste_2
#Hier beginnt das Hauptprogramm
grenze = int(input("Obergrenze: "))
for i in range(2,grenze+1):
anzahl = 0
if prim(i) == True:
continue
else:
primfaktorzerlegung(i)
for j in range(len(primfaktorzerlegung(i))):
if (i/primfaktorzerlegung(i)[j] - 1) % primfaktorzerlegung(i)[j] == 0:
anzahl += 1
if anzahl == len(primfaktorzerlegung(i)):
print(i,"=",primfaktorzerlegung(i))
Diese Version ist um bis zu 6 Mal performanter, vor allem bei großen Zahlen.
Python-Code
Python-Code
import math
primzahlen = []
def prim(zahl):
if zahl == 2:
return True
elif zahl % 2 == 0:
return False
else:
for i in range(3,int(math.sqrt(zahl)) + 1,2):
if zahl % i == 0:
return False
return True
def primfaktorzerlegung(zahl):
liste_pfz = []
if len(primzahlen) == 0:
for i in range(2,int(grenze/2) + 1):
if prim(i) == True:
primzahlen.append(i)
for i in primzahlen:
if prim(zahl) == True:
liste_pfz.append(int(zahl))
break
elif zahl != 1:
while zahl % i == 0:
liste_pfz.append(i)
zahl /= i
else:
break
return liste_pfz
#Hier beginnt das Hauptprogramm
grenze = int(input("Obergrenze: "))
for i in range(2,grenze + 1):
anzahl = 0
if prim(i) == True:
continue
else:
primfaktorzerlegung(i)
for j in range(len(primfaktorzerlegung(i))):
if (i/primfaktorzerlegung(i)[j] - 1) % primfaktorzerlegung(i)[j] == 0:
anzahl += 1
if anzahl == len(primfaktorzerlegung(i)):
print(i, "=", primfaktorzerlegung(i))