Das deutsche Python-Forum

Ich habe mir einen Algorithmus gebastelt und den möchte ich nun ausprobieren, mit Python selbstverständlich. Nur bei einer Sache bin ich mir unsicher, gibt es unter Python eine möglichkeit, ganze Zahlen zu faktorisieren?

Hat jemdan vlt eine Idee für mich? Danke

ja die Möglichkeit gibt es, das Zauberwort heißt Modulus (Division mit ganzzahligem Rest)

Code: Alles auswählen

In [1]: x = 10 % 3

In [2]: x
Out[2]: 1

Wenn dir die Methode der Elliptischen Kurve zur faktorisierung was sagt, dann guckt dir mal PyECM an.

hast du zufällig noch einen Link, der mir das Modul erklärt? Scheint genau das zu sein was ich suche

mein vorheriger Beitrag hat sich erledigt, hab alles gefunden.....
Besten Dank!!
Jetzt muss ich nur noch rausfinden, wie man unter Python eine Zahl überprüft, ob diese eine Primzahl ist oder nicht. Dann habe ich alle meine fehlenden Sachen zusammen.

BlackMamba hat geschrieben:Jetzt muss ich nur noch rausfinden, wie man unter Python eine Zahl überprüft, ob diese eine Primzahl ist oder nicht. Dann habe ich alle meine fehlenden Sachen zusammen.

Na dann ist das Problem auch schon erledigt.

hab jetzt alles zusammen, weiß nur nicht, wie ich PyECM in meinem Programm mit integrieren kann.
Ich will nämlich eine Zahl, z.B. 48 faktorisieren und dann überprüfen, ob einer der Faktoren eine Primzahl ist. Wie ich das mache, also eine Zahl zu überprüfen, habe ich gerade rausgefunden und auch eben geschrieben.

Nur leider bin ich nicht gut genug in Python um bei PyECM durchzusteigen.

Vlt könnte einer von euch da mal einen Blick drauf werfen, dass ist mir wirklich (noch, ich bin ja feißig am lernen) eine Nummer zu groß... Sorry...

Eigendlich brauche ich nur den Teil, der die Faktoren bestimmt, die würde ich dann am liebsten in einem Array abspeichern, damit ich da gut drauf zugreifen kann.
Dann die Sache mit den Primzaheln und die anderen beiden Sachen zu integrieren, ist dann kein Problem, nur PyECM ist etwas zu hoch für mich.

list(pyecm.ecm(zahl)) liefert z.B. eine Liste der Faktoren der Zahl zahl.
MfG
HWK

Eine naive (und für große Zahlen ineffiziente) Methode ist

Code: Alles auswählen

def factorize(n): # wir überprüfen nicht, ob n ganzzahling und >0 ist, das müsste man aber eigentlich machen
	if n == 1:
		return [] #1 hat keine (prim)faktoren
	if n % 2 == 0:
		return [2] + factorize(n/2)
	else:
		for p in xrange(3, int(sqrt(n))+1, 2):
			if n % p == 0:
				return [p] + factorize(n/p)
		# wenn wir bis hierhin kommen, ist n prim
		return [n]

print factorize(99) # [3, 3, 11] 99 = 3 * 3 * 11
print factorize(7 * 11 * 13) # [7, 11, 13]
print factorize(1234567891) # [1234567891], ja das ist eine Primzahl
print factorize(31337) # [31337], und das auch, wie leet ;)

Zuerst werden die Sonderfälle 1 und eine gerade Zahl überprüft (eine gerade Zahl ist nicht unbedingt ein Sonderfall, aber so brauchen wir in der Hauptschleife nur ungerade Teilerkandidaten auszuprobieren).

Ansonsten wird einfach nacheinander versucht, durch eine ungerade Zahl zu teilen. Sobald ein Faktor (sagen wir einfach mal 7) gefunden wurde, wird er zusammen mit der Liste der Faktoren der Zahl n/7 zurückgegeben. Die Faktoren der Zahl n/7 werden ebenfalls durch die Funktion berechnet, es ist also eine rekursive Funktion.

Wenn bis sqrt(n) + 1 kein Faktor gefunden wurde, muss die aktuelle Zahl, die wir überprüfen, eine Primzahl sein. Warum?

Sagen wir mal, es gäbe eine Zahl N, die nur Faktoren hat, die größer als sqrt(N) sind.
Sei f nun ein beliebiger dieser Faktoren, dann gilt

N = f * rest, da f > sqrt(N) ist, gilt N > sqrt(N) * rest
---> N / sqrt(N) > rest
---> sqrt(N) > rest.

rest ist wegen N = f * rest aber auch ein Faktor von N aber kleiner als sqrt(N) -> Widerspruch.

Ich hoffe, du hast jetzt eine gute Vorlage, die zu selber weiterentwickeln kannst. Man kann diesen Algorithmus z. B. noch verbessern/beschleunigen, indem man nur durch Primzahlen zu teilen versucht.

PS: Die Zeile "if n % p == 0:" und die folgende könnte man auch so schreiben:

Code: Alles auswählen

x,rest = divmod(n,p)
if rest == 0:
    return [p] + factorize(x)

so spart man sich eine extra Rechenoperation

Ich hatte eine ähnliche Variante entworfen:

Code: Alles auswählen

from math import sqrt

def fact(n):
    if n > 3:
        for i in range(2, int(sqrt(n)) + 1):
            a, b = divmod(n, i)
            if b == 0:
                return ([i] + fact(a))
    return [n]

Vorher wollte ich es mit Generatoren schreiben:

Code: Alles auswählen

from math import sqrt

def fact(n):
    if n > 3:
        for i in range(2, int(sqrt(n)) + 1):
            a, b = divmod(n, i)
            if b == 0:
                yield i
                fact(a)
                return
    yield n

Scheinbar ruft fact(a) nach yield i aber nicht die Prozedur auf. Warum?
MfG
HWK

HWK hat geschrieben:Scheinbar ruft fact(a) nach yield i aber nicht die Prozedur auf. Warum?

When a yield statement is executed, the state of the generator is frozen and the value of expression_list is returned to next()'s caller. By ``frozen'' we mean that all local state is retained, including the current bindings of local variables, the instruction pointer, and the internal evaluation stack: enough information is saved so that the next time next() is invoked, the function can proceed exactly as if the yield statement were just another external call.

( http://docs.python.org/ref/yield.html )

yield pausiert deine Funktion und gibt "i" an die aufrufende Funktion zurück. yield kann man somit als "return mit Pausefunktion" betrachten
erst wenn du die next()-Methode des Generators aufrufst, wird wie gewünscht, fact(a) aufgerufen.
außerdem ist ein return nach yield überflüssig.

@rico: Das ist nicht die Erklärung. Beim nächsten next wird ja nach dem yield fortgesetzt. Das Problem ist aber, dass fact einen Generator und kein neues Element zurückliefert. So funktioniert es:

Code: Alles auswählen

from math import sqrt

def fact(n): 
    if n > 3: 
        for i in range(2, int(sqrt(n)) + 1): 
            a, b = divmod(n, i) 
            if b == 0: 
                yield i 
                for x in fact(a):
                    yield x
                return 
    yield n

list(fact(110))

Das return nach yield ist schon notwendig, da sonst die for-Schleife fortgesetzt wird.
MfG
HWK

Das deutsche Python-Forum

Faktorisierung

Faktorisierung