Primfaktorzerlegung!? Hilfe!

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Dreavel
User
Beiträge: 4
Registriert: Mittwoch 7. Februar 2007, 08:06

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!
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

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
Zuletzt geändert von birkenfeld am Mittwoch 7. Februar 2007, 09:36, insgesamt 1-mal geändert.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Dreavel
User
Beiträge: 4
Registriert: Mittwoch 7. Februar 2007, 08:06

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
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Zeile 7 muss lauten:

Code: Alles auswählen

zahl /= test
MfG
HWK
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Stimmt. Ja, so ist das, wenn man vor dem Frühstück noch programmiert ;)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

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
Dreavel
User
Beiträge: 4
Registriert: Mittwoch 7. Februar 2007, 08:06

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!
autos
User
Beiträge: 4
Registriert: Mittwoch 14. Februar 2007, 08:09

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
XNiemannX
User
Beiträge: 1
Registriert: Mittwoch 14. Februar 2007, 08:40

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 =)
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

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
Dreavel
User
Beiträge: 4
Registriert: Mittwoch 7. Februar 2007, 08:06

böööööööööööh das ist fies man versteht es halt nicht
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

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 :roll:

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!
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

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
autos
User
Beiträge: 4
Registriert: Mittwoch 14. Februar 2007, 08:09

ich versteh es immer noch nicht
Zuletzt geändert von autos am Montag 26. Februar 2007, 13:02, insgesamt 1-mal geändert.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

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
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
autos
User
Beiträge: 4
Registriert: Mittwoch 14. Februar 2007, 08:09

hey leondias, du hattest denke ich ein paar hilfsmittel zum lernern, vielleicht ein buch. hast du ein buchtipp den auch wirklich eher minderbegabte verstehen?
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

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
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

autos hat geschrieben:hey leondias
Bin zwar nicht leondias, aber da die Levenshtein-Distanz zu Leonidas nicht so groß ist antworte ich dennoch :roll:
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.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Groucho
User
Beiträge: 9
Registriert: Donnerstag 15. Februar 2007, 14:44

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
Antworten