Eulersche Funktion und Python

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.
Antworten
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

Hallöle,
Hätte gleich nocheine Frage, ist es möglich die Eulersche φ-Funktion in Python zu benutzen, wenn ja wie geht das und vlt könntet ihr mir ein Beispiel geben damit ich das besser nachvollziehen kann.
Mfg Impi
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

Ich verdeutliche das einfach mal.
Ich möchte eine Zahl finden die keinen gemeinsamen teiler außer 1 zu den Zahlen a, b, c hat bsw. 2,6,12,.
In diesem falle wäre eine möglichkeit die Zahl 5 aber wie kann ich diese doch recht schwere Aufgabe so in mein Programm bringen das diese Zahl von meinem Imput abhänig berechnet werden?
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Naja Strenggenommen suchst du nicht die Eulersche Funktion, die gibt die Anzahl der positiven, teilerfremden, natürlichen Zahlen von 1 bis n zurück.
Also 1 <= a <= n wobei dann eben für a gelten muss, dass ggT(a, n) = 1 ist.
So ähnlich steht das auch auf Wikipedia.
Und da steckt eigentlich auch schon die Lösung für dein Problem drin.
Die Bedingung, dass a Teilerfremd ist, wird hier mit ggT(a, n) = 1 angegeben.
Was du jetzt machen müssest, wäre eine funktion für den ggT zu schreiben und diese anschließend anzuwenden.
Eigentlich recht einfach, wenn du da nicht weiterkommst, hilft Google oder Wikipedia bestimmt, ist nicht's besonders schweres.

(Edit: < zu <= richtig gestellt, auch wenn's eh keinem auffällt und keinen interessiert)
Zuletzt geändert von Nocta am Samstag 19. Juli 2008, 00:55, insgesamt 1-mal geändert.
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

danke danke :D
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

Hmm habe mir jetz eine Funktion geschrieben

Code: Alles auswählen

def pubKey_ggt(p, q):
    a = int(p)
    b = int(q)
    
    while  b>0:
        a, b = b, a%b
        return p, q
Aber ich bekomm immer den größten Wert der Variabelen raus??
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Deine Funktion kann man zu

Code: Alles auswählen

def ggt(p,q):
  if q > 0: return p, q
zusammenstreichen. Das sollte dir erklären, warum du nicht das erhälst, was du hoffst zu erhalten.

Stefan
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

Hmm also bei mir gehts immernoch nicht jetz bekomme ich als ergebnis
('3\r', '9\r') raus?

Code: Alles auswählen

def pubKey_ggt(p,q):
    if q > 0: return p, q

pubKeyOutput_ggt = pubKey_ggt(p, q)
print pubKeyOutput_ggt

BlackJack

sma hat Dir gesagt, dass das zu Deinem Quelltext äquivalent ist, wie soll dann auch ein richtiges Ergebnis heraus kommen. Du müsstest mal nachdenken und nachvollziehen, *warum* das Ergebnis jeweils heraus kommt und warum die beiden Funktionen das gleiche Ergebnis heraus bekommen, wenn man die Eingabe vor dem Aufruf von sma's Funktion in Zahlen umwandeln würde.

Das solltest Du übrigens ausserhalb der Funktionen machen. Funktionen, die mit Zahlen rechnen sollten auch solche als Argumente bekommen und keine Zeichenketten.
ProgChild
User
Beiträge: 210
Registriert: Samstag 9. April 2005, 10:58
Kontaktdaten:

Impi hat geschrieben:Hmm habe mir jetz eine Funktion geschrieben
Wie sieht es denn damit aus? Ohne es getestet zu haben:

Code: Alles auswählen

def pubKey_ggt(p, q):
    a = int(p)
    b = int(q)
    
    while  b>0:
        a, b = b, a%b
    return a
Der Euklidische Algorithmus ist halt nicht ganz so leicht zu verstehen, bzw. zu Beweisen.
Es ist nett, freundlich zu sein.
Auch nett: [url=http://www.progchild.de]Homepage[/url]
Impi
User
Beiträge: 10
Registriert: Sonntag 22. Juni 2008, 19:16

Das Problem ist gelöst es klappt wunderbar :P

Code: Alles auswählen

def pubKey_ggt(a, b):
    while b>0:
        a, b = b, a%b
    return a
und im Hauptprogramm die Variabelen in Int umgewandelt
Antworten