Giuga-Zahlen berechnen

2 Lösungen

#68

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

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von jigga (4260 Punkte) - 23.06.2015 um 08:29 Uhr

Diese Version ist um bis zu 6 Mal performanter, vor allem bei großen Zahlen.

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))