Seite 1 von 2
Primfaktorzerlegung!? Hilfe!
Verfasst: Mittwoch 7. Februar 2007, 08:23
von Dreavel
Also ich habe folgendes Problem:
Ich sitze gerade im Informatik Kurs und unser Lehrer hat uns die Aufgabe aufgetragen ein Programm zu erstellen, welches die Faktorzerlegung von den Zahlen zu stande bringen soll, die keine Primzahlen sind. Wir haben es schon so weit gebracht, dass wir ein Programm erstellt haben, welches zwischen zwei Intervallen unterscheiden kann was eine Primzahl ist und was keine Primzahl ist.
(Achja bevor ich es vergesse! Es ist wichtig, dass das Programm aus mehreren Definitionenteilen besteht.)
Code: Alles auswählen
#primzahl.py name des programms
# im folgenden benötigt das programm die quadratwurzel
from math import *
# die funktion primzahl wird definiert. sie testet ob die zahl eine primzahl ist
def primzahl (zahl):
if zahl <= 2:
prim = 1
else:
for i in range(2,int(sqrt(zahl))+1):
if zahl%i == 0:
prim = 0
break
else:
prim = 1
return prim
# die funktion eingabe nimmt die intervallgrenzen auf und gibt sie weiter
def eingabe():
print "Ich ermittle alle Primzahlen in einen Intervall"
a=input("Untere Intervallgrenze: ")
b=input("Obere Intervallgrenze: ")
return(a, b)
# die funktion verarbeitung sorgt dafür, dass die zahlen innerhalb der intervallgrenzen untersucht werden
def verarbeitung(intervall):
prim=[] # gefundene primzahlen werden in der liste prim gesammelt,sie ist zunächst leer
for i in range(intervall[0], intervall[1]+1):
if primzahl(i): # hier arbeit die funktion primzahl
prim+=[i] # die liste prim wird um das element i - eine weitere primzahl- erweitert
return prim
# die funktion ausgabe sorgt dafür, dass die primzahlen auf dem bildschirm erscheinen
def ausgabe(primzahlen):
print"Primzahlen:"
for zahl in primzahlen:
print zahl, # das komma bewirkt, dass alle elemente der liste hinter- und nicht untereinander geschrieben werden
# hauptprogramm : dieser kleine dreizeiler ist das eigentliche programm
intervall=eingabe() # die eingegebenen intervallgrenzen sind jetzt auch intervallgrenzen
primzahlliste=verarbeitung (intervall) # die berechneten primzahlen sind eine liste
ausgabe (primzahlliste) # die liste wird ausgegeben
Danke!
Verfasst: Mittwoch 7. Februar 2007, 08:52
von birkenfeld
Grundsätzlich gehst du so vor:
Code: Alles auswählen
zahl = 768 # z.B.
test = 2
primfaktoren = []
while zahl > 1:
while zahl % test == 0:
zahl %= test
primfaktoren += [test]
test += 1
Dabei können nur Primzahlen als Primfaktoren auftreten.
Wenn du allerdings die Liste der Primzahlen bis "zahl" schon berechnet hast, kannst du auch einfach die Elemente der Liste nehmen, anstatt test hochzuzählen:
Code: Alles auswählen
zahl = 768 # z.B.
primzahlen = [2, 3, 5, ...]
i = 0
primfaktoren = []
while zahl > 1:
while zahl % primzahlen[i] = 0:
zahl %= primzahlen[i]
primfaktoren += [primzahlen[i]]
i += 1
Verfasst: Mittwoch 7. Februar 2007, 09:08
von Dreavel
tut mir leid hab das nun nicht so ganz verstanden muss nun aber weg...
achja und ich glaube es sollte test == 0 heißen
mfg
Dreavel
Verfasst: Mittwoch 7. Februar 2007, 13:59
von HWK
Zeile 7 muss lauten:
MfG
HWK
Verfasst: Mittwoch 7. Februar 2007, 14:20
von birkenfeld
Stimmt. Ja, so ist das, wenn man vor dem Frühstück noch programmiert
Verfasst: Mittwoch 7. Februar 2007, 14:37
von rayo
Hi Dreavel
Warum schreibst du mir eine PM?
Ehrlich finde ich das recht mühsam, ich interessiere mich nicht dafür und du hast inzwischen schon gute Antworten gekriegt.
Dadurch wirst du sicher nicht schneller eine Antwort kriegen.
Gruss
Verfasst: Mittwoch 14. Februar 2007, 08:00
von Dreavel
Hi ich bin's noch einmal
ich wollte nun fragen wo ich genau das Programm einfügen muss
ich denke mir einmal, dass es
for i in range(2,int(sqrt(zahl))+1):
if zahl%i == 0:
prim = 0
break
vor break noch stehen muss
(vllt könntet ihr es einmal fertig in dem Programm posten, was ich am Anfang angeführt habe)
Danke!
Verfasst: Mittwoch 14. Februar 2007, 08:17
von autos
hallo ich habe eine ähnliche frage wie draevel.
eigentlich die gleiche.
ich muss ein programm erstellen, in dem eine zahl mit der primfaktorzerlegung zerlegt wird. dabei soll man die einzelnen rechenschritte sehen.
es würde mich freuen wenn iihr schnell antwortet
Hilfe!
Verfasst: Mittwoch 14. Februar 2007, 08:55
von XNiemannX
hi,
ich finde die frage von dreavel sehr gut, da auch ich im moment eine ähnliche aufgabe zu lösen habe, wie dreavel. Sind wir etwa im selben informatikkurs? ^^ ich hoffe, dass bald einer von euch profis
uns anfängern hilft =)
Verfasst: Mittwoch 14. Februar 2007, 09:02
von rayo
Hi
Also eine Primzahlliste ist ja schon im ersten Post vorhanden und Birkenfeld mit der Korrektur von HWK haben auch schon eine Lösung gepostet.
Was braucht ihr denn? Eine fertige Lösung werdet ihr nicht kriegen.
Gruss
Verfasst: Mittwoch 14. Februar 2007, 09:10
von Dreavel
böööööööööööh das ist fies man versteht es halt nicht
Verfasst: Mittwoch 14. Februar 2007, 09:11
von nkoehring
Hallo...
ich finde es interessant, dass ich jetzt schon zum zweiten mal hier Python als LehrSprache fuer den Informatikkurs vorfinde. Tolles Ding. Bei mir gabs das leider nicht und mein Professor ist auch nicht unbedingt ueberzeugt von Python. Er ist halt eher der Java-Mensch
Naja, also ich hab leider keine Zeit, da ich gleich ne Pruefung habe. Ansonsten sind aber eigentlich wirklich schon alle Antworten da, die ihr braucht.
Das tolle an Python ist doch, dass man ohne großen Aufwand probieren kann... also tut euch keinen Zwang an. Schmeißt den Code zusammen, versucht ihn zu buegeln bis ihr denkt, er stimmt und dann probiert solang, bis keine Exceptions mehr auftreten
=> Learning By Doing nennt man das!
Verfasst: Mittwoch 14. Februar 2007, 09:16
von rayo
Dann sag was du nicht verstehst und zeig deinen Code was du bis jetzt hast.
Du machst am besten eine neue Funktion, die 2 Parameter hat, eine Liste von Primzahlen und die Zahl, die in Primfaktoren zerlegt werden soll.
Code: Alles auswählen
def factor(primzahlen, zahl):
primfaktoren = []
while zahl > 1:
while zahl % primzahlen[i] = 0:
zahl %= primzahlen[i]
primfaktoren += [primzahlen[i]]
i += 1
Gruss
Verfasst: Mittwoch 14. Februar 2007, 19:01
von autos
ich versteh es immer noch nicht
Verfasst: Mittwoch 14. Februar 2007, 19:11
von rayo
Hi
Und was ist mit selber lernen?
Lesen ist halt zuerst an der Reihe, man muss sich halt informieren.
Viele lernen programmieren in dem sie Anleitungen lesen und dann viel damit ausprobieren.
Und Python ist super wenn es um ein wenig auszuprobieren geht.
Gruss
Verfasst: Mittwoch 14. Februar 2007, 20:39
von Leonidas
autos hat geschrieben:Learning By Doing wie soll man denn was doen, wenn der lehrer uns nicht mal die grundlagen erklären kann.
Das konnte mein Lehrer auch nicht. Hey, Moment, mein Lehrer hat mir gar kein Python beigebracht. Wenn ich so darüber nachdenke - ich hatte nicht einmal einen Informatik-Lehrer.
Python habe ich mir selbst beigebracht wie sicherlich eine Große Mehrheit der User hier. Scheint also durchaus möglich zu sein.
Verfasst: Freitag 16. Februar 2007, 16:46
von autos
hey leondias, du hattest denke ich ein paar hilfsmittel zum lernern, vielleicht ein buch. hast du ein buchtipp den auch wirklich eher minderbegabte verstehen?
Verfasst: Freitag 16. Februar 2007, 17:01
von CM
Bücher gibt es wie Sand am Meer - eine Suche hier im Forum würde Dir auch schon Hits geben. Ansonsten gibt es das [wiki=FAQ#WieFangeIchAlsEinsteigerAn]wiki[/wiki], das ein paar deutschsprachige Einsteigerinfos offeriert. Aber das
offizielle Tutorial ist eigentlich auch schon sehr gut.
Gruß,
Christian
Verfasst: Freitag 16. Februar 2007, 17:44
von Leonidas
autos hat geschrieben:hey leondias
Bin zwar nicht leondias, aber da die Levenshtein-Distanz zu Leonidas nicht so groß ist antworte ich dennoch
autos hat geschrieben:du hattest denke ich ein paar hilfsmittel zum lernern, vielleicht ein buch.
Ich hatte VB6-Erfahrung (das VB-Wissen kann man zwar wegwerfen, aber Programmierwissen ist Programmierwissen). Für Lektüren kannst du mal [wiki]FAQ#DeutschsprachigeLektrenImNetz[/wiki] konsultieren. Ich selbst habe eine alte Ausgabe von Learning Python, aber ich habe Python hauptsächlich durch Online-Tutorials und Learning-by-doing gelernt, so dass ich das Buch selbst kaum gelesen habe.
Verfasst: Sonntag 18. Februar 2007, 12:18
von Groucho
Für eine Primzahlzerlegung bietet sich eine rekursive Funkion an, weil das Problem sich nach dem Auffinden des ersten Faktor auf ein einfacheres Problem reduziert. Zum Beispiel
Code: Alles auswählen
from math import sqrt
def zerlege(zahl,start_faktor=2,faktor_liste=[]):
if start_faktor <= sqrt(zahl):
if start_faktor == 2:
if zahl%2 == 0:
return zerlege(zahl/2,2,faktor_liste+[2])
else:
start_faktor = 3
for faktor in xrange(start_faktor, int(sqrt(zahl))+1,2):
if zahl % faktor == 0:
return zerlege(zahl/faktor,faktor,faktor_liste+[faktor])
return faktor_liste +[zahl]
# zerlege Zahlen von 2 bis 30
for i in xrange(2,31):
ergebnis = zerlege(i)
if i == ergebnis[0]:
print i, "ist prim"
else:
print i, "=", reduce(lambda a,b: str(a)+"*"+str(b),ergebnis)
Man müsste die zerlege-Funktion eigentlich auch schreiben können, ohne der Funktion eine Liste der bisher gefundenen Primfaktoren mitzugeben, aber ich sehe im Moment nicht wie.
Gruß, Groucho