Was ist falsch an meinem code?

[Gwunderi]

Durch Deine for-Schleife hast Du die »and«-Verknüpfung in eine »or«-Verknüpfung umgewandelt.

Ach so, und da alle anderen geprüften Zahlen keine Teiler von 486'847 sind, wird sie ausgegeben. Hatte ja schon gesehen, dass die Lösungen gleich mehrfach ausgegeben werden, dachte mir aber, es sei weil jetzt jede Zahl einzeln geprüft wird, was ja auch stimmt - aber dass die "and"-Verknüpufng damit auch verlorengeht ... wäre eigentlich logisch. (Und da es dieselben Ergebnisse lieferte, habe ich gar nicht weiter überlegt.)

Tut mir leid, wenn ich da verschlimmbessere, aber das kleine Genie Eliazz wird sich wohl nicht so leicht verwirren lassen.

Gibt es denn auch eine Möglichkeit, bei einer Array, deren Elemente mit "and" geprüft werden, das in nur einem Schritt zu tun?

[Sirius3]

@BlackJack: »div« teilt das 128bit-Register rdx:rax durch rcx. Siehe auch http://download.intel.com/products/proc ... 253666.pdf Seite 293.
Daher müssen die oberen 64bit null sein. Das Ergebnis liegt dann in rax und der Rest der Division in rdx.

@Gwunderi:

Code: Alles auswählen

if all(a%x>0 for x in prime_proof): ...

[Gwunderi]

Danke für den Code Sirius

Dann geht es doch so (hoffe ich wenigstens, bei den geprüften Zahlen stimmt es mal):
Da man in "primteiler" eine Anfangszahl eingeben muss, habe ich 2 eingesetzt, daher muss man bei einer ungeraden Zahl daran denken, die 2 aus den Lösungen zu streichen.
Nur geht es bei hohen Zahlen (z.B. der von Eliazz) eine halbe Ewigkeit.
Sollte man also noch eine Methode einbauen, dass man bei jeder neu gefundenen Primzahl die Vielfachen davon vor dem neuen Prüfgang aussiebt (wahrscheinlich ist es das, was einige User hier gemeint haben?)

Code: Alles auswählen

primteiler = [2]

n = int(input("Gib eine ganze Zahl ein: "))

a = 3
        
while a <= n/2:
    if all(a%x > 0 for x in primteiler) and n%a == 0:
            primteiler.append(a)
    a = a + 2
print(primteiler)

Habe es mit folgenden Zahlen ausprobiert:
15015 (=3*5*7*11*13)
10010 (=2*5*7*11*13)
60030 (=2*3*5*23*29)
6040 (gibt 2, 5, 151 heraus)

[snafu]

Ich poste jetzt auch einfach mal eine mögliche Python-Lösung, diesmal orientiert an Euklid (was ja eigentlich auch das naheliegendste ist):

Code: Alles auswählen

from itertools import count, takewhile

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    for candidate in takewhile(lambda i: i <= n, count(2)):
        while n % candidate == 0:
            n /= candidate
    return candidate

[Hirschin]

Hallo zusammen,

Habe auch ein paar Anmerkungen:
Will man prüfen, OB eine Zahl n eine Primzahl ist, genügt es, bis zur Wurzel von n zu prüfen.
Aber um die grösste Primzahl, die Teiler von n ist herauszufinden genügt es nicht, habe ich eben herausgefunden.
Nehmen wir z.B. 33 - ist 33 eine Primzahl? da genügt es, bis 6 zu prüfen, denn 11 * 3 wurde schon bei der 3 geprüft.
Aber die grösste Primzahl, die Teiler von 33 ist - also 11 - würde man hier glatt "übersehen".

Man muss also doch, wie BlackJack anfangs meinte, bis n/2 prüfen!
]

Jaja, lang lang ist es her mit den Primzahlen!
Mit Hilfe der Primfaktorzerlegung wird eine natürliche Zahl in ein Produkt von Primzahlen zerlegt, zum Beispiel ist 24 = 2*2*2*3. Ein Primfaktor muss also zwei Bedingungen erfüllen: Erstens muss ein Primfaktor eine Primzahl sein. 4 kann also kein Primfaktor sein, da sie sich weiter in 2*2 zerlegen lässt. Zweitens muss ein Primfaktor ein Teiler dieser natürlichen Zahl sein. Die Zahl muss also ohne Rest durch den Primfaktor teilbar sein.
(Quelle:http://primfaktorzerlegung.net/)

[Sirius3]

die etwas schnellere Variante:

Code: Alles auswählen

from itertools import count, takewhile, chain

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    sqn=n**0.5
    for candidate in takewhile(lambda i: i <= sqn, chain((2,), count(3, 2))):
        while n % candidate == 0 and n>candidate:
            n /= candidate
            sqn=n**0.5
    return n

[snafu]

@Sirius3: Jepp, deine Version gibt besonders bei großen Primzahlen Vollgas - zumindest im Gegensatz zu meiner Variante. Danke fürs Posten.

Aber das zweite `sqn=n**0.5` macht innerhalb der `while`-Schleife wohl wenig Sinn. Hat zwar keine Riesen-Auswirkungen, aber es sollte IMHO an die Stelle *nach* der `while`-Schleife gesetzt werden. Also quasi kurz bevor die `for`-Schleife ihren nächsten Iterationsschritt macht.

Außerdem verstehe ich nicht, wieso das zusätzliche `and` nötig ist. Wenn man `candidate` zurückliefert, müsste es doch auch ohne den `and`-Teil korrekt funktionieren, oder nicht?

Insgesamt sähe es dann so aus:

Code: Alles auswählen

from itertools import chain, count, takewhile

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    sqn = n**.5
    candidates = chain([2], count(3, 2))
    for candidate in takewhile(lambda i: i <= sqn, candidates):
        while n % candidate == 0:
            n /= candidate
        sqn = n**.5
    return candidate

EDIT: Ich merke gerade, dass man wohl doch nicht einfach so den `candidate` als Rückgabe nehmen kann...

[jerch]

@snafu:
Die Wurzel innerhalb der Schleife ist wichtig. Ausserhalb würdest Du für jeden Kandidaten das Suchfenster verkleinern, egal ob Teiler oder nicht.
Die UND-Bedingung ist da nötig, da ansonsten n auf eins fallen würde, da der letzte verbleibende Faktor modulo sich selber ja null ergibt und im Schleifenkörper dann durch sich selbst geteilt würde.
Den letzten Kandidaten kannst Du nicht einfach zurückgeben, der wäre nur für eine Quadratzahl richtig. Das "verbliebene" n ist der letzte Teiler.

Eine gegen 2*3 ausgerichtete Version ist etwa doppelt so schnell, dafür aber der Code deutlich länger.

Hier mal die komplette Faktorisierung (mit while, da doch einiges schneller):

Code: Alles auswählen

from math import sqrt

def prime_factors(n):
    sq_n = sqrt(n)
    counter = 0
    candidate = 2
    while candidate <= sq_n:
        while not n % candidate:
            n /= candidate
            sq_n = sqrt(n)
            counter += 1
        if counter:
            yield (candidate, counter)
            counter = 0
        if candidate == 2:
            candidate += 1
        else:
            candidate += 2
    if n > 1:
        yield (n, 1)

def pprint_factors(factors):
  return ' * '.join('%d^%d' % (b, e) if e > 1 else '%d' % (b,)
                    for b, e in factors)

Edit: Seh grad, dass ich die 2 vergessen habe Fixed

[snafu]

@jerch: Ist das so gewollt, dass deine Funktion teilweise Faktoren liefert, die nicht-prim sind?

EDIT: Deine editierte Variante liefert für 9 immer noch (9, 1).

@Meine Codeanmerkungen an Sirius3: Ja, da hatte ich wohl Tomaten auf den Augen, um nicht zu sehen, dass das Wurzelziehen abhängig von einer sich verändernden Größe ist...

[jerch]

@snafu: Na klar, war das Absicht, wollt testen, ob Du's merkst Da fehlte ein '='

[snafu]

Wie das so ist mit nicht-trivialen Optimierungen: Sie mögen nötig sein wegen der Verarbeitungzeit für große Eingaben, aber man steigt auch immer schlechter durch den Code.

Jetzt scheint (auf dem ersten Blick) aber alles ok zu sein.

[jerch]

Wie das so ist mit nicht-trivialen Optimierungen: Sie mögen nötig sein wegen der Verarbeitungzeit für große Eingaben, aber man steigt auch immer schlechter durch den Code. ...

Liegt wohl eher am Hinrotzen

[Sirius3]

Ganz schön anstrengend, nochmals einen Faktor 5 in der Geschwindigkeit rauszuholen:

Code: Alles auswählen

def prime_factors(num):
    result=[]
    for k in (2,3,5):
        while num%k==0: num //= k; result.append(k)
    sqn=int(num**0.5)
    k=7
    while k<=sqn:
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 6
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 6
    if num!=1:
        result.append(num)
    return result

[jerch]

Mehr dürfte mit Python und dieser Methode (wheel factorisation) kaum drin sein. Nimmt man die 7 mit hinzu, kann man zwar mehr eliminieren, allerdings ist das Pattern dann schon 210 groß und der Gewinn marginal (77% vs. 73% für 2*3*5). Die Eliminationrate wächst nur gering, während die 'wheels' riesig werden.

[Gwunderi]

Hallo zusammen,

Hier noch mein Programm zur allgemeinen Erheiterung:
Wenn man Glück hat, kann es die Primfaktoren auch von 12-stelligen Zahlen in Sekundenschnelle finden, sogar für eine 15-stellige Zahl (679555042947243) braucht es keine halbe Minute, oder für die 18-stellige (879679555042947243) etwa 2 Minuten. Glück hat man, falls n / (Produkt der Primfaktoren bis 1 Mio.) kleiner als etwa 10'000 ist.
Es ist mir bewusst, dass man ein Programm nicht so schreibt, auch formal nicht : )

Das Programm von Sirius werde ich bald einmal versuchen nachzuvollziehen (geht glaube ich so vor: jedesmal wenn ein Primfaktor von n gefunden wurde, wird n durch diesen Faktor dividiert ... aber weiter sehe ich es im Moment nicht.)

Viel Spass und Grüsslein
Gwunderi

Code: Alles auswählen

primteiler = [2]        

n = int(input("Gib eine grosse Zahl ein: "))

a = 3

while a <=1000000:
        if all(a%x > 0 for x in primteiler) and n%a == 0:
                primteiler.append(a)
        a = a + 2

if n%2 > 0:
        primteiler.remove(2)
print("Erste Primfaktoren bis 1'000'000: ",primteiler)                          

# nur falls grösster gefundener Primfaktor < n**0.5:

if primteiler[-1] < n**0.5:        
        
        p = 1
        for i in primteiler:
            p *= i
        print("Produkt Primfaktoren bis 1'000'000 = ", p)

        print("n durch Produkt: ",n/p)  

        if n/p == 1:
            print("Das waren alle Primfaktoren von n")
        else:
            if n/p < 10000000:
                print("Die restlichen kommen gleich.")
            if n/p > 10000000 and n/p < 100000000:
                print("Es könnte einige Minuten dauern.")
            if n/p > 100000000:
                print("Dauert zu lange - siehe Programm von Sirius")

            a = 3
        
            while a <= n/p:
                if all(a%x > 0 for x in primteiler) and n%a == 0:
                    primteiler.append(a)
                a = a + 2

            print(primteiler)

[BlackJack]

@Gwunderi: Dein Hauptproblem, abgesehen von den vielen Sonderfällen die da unnötigerweise unterschieden werden, ist dass Du `n` nicht verkleinerst wenn Du einen Faktor gefunden hast. Dadurch testest Du deutlich mehr Teiler als nötig.

Und Du erzeugst dadurch auch mehr Primzahlen als nötig. Das kann man auf das Nötigste begrenzen in dem man das Programm so schreibt, dass jede gefundene Primzahl sofort nach dem sie gefunden wurde, verwendet wird um `n` zu verkleinern.

In funktionalen Programmiersprachen (die nicht „lazy” sind, wie Haskell) kann man das über eine Rückruffunktion lösen. An dieser Stelle möchte ich mich für meine JavaScript-Lösung entschuldigen, die umständlicher geschrieben ist, als das üblich wäre. Hier eine typischere und einfacher formulierte Variante für JavaScript:

Code: Alles auswählen

#!/usr/bin/env node
'use strict';
var _ = require('underscore');

Number.prototype.divides = function(n) { return n % this == 0; };

var primes = function (callback) {
    var primes = [];
    var candidate = 3;
    var testCandidate = function (prime) { return !prime.divides(candidate); };
    var stop = callback(2);
    while (!stop) {
        if (_(primes).every(testCandidate)) {
            primes.push(candidate);
            stop = callback(candidate);
        }
        candidate += 2;
    }
};

var factor = function (n) {
    var result = [];
    primes(function (prime) {
        if (prime.divides(n)) {
            result.push(prime);
            while (n > 1 && prime.divides(n)) n /= prime;
        }
        return n == 1;
    });
    return result;
};

var main = function () { console.log(factor(parseInt(process.argv[2]))); };

main();

In objektorientierten Sprachen gibt es in der Regel das Konzept von Iteratoren, also Objekte mit einer Methode, welche das nächste Element von etwas liefern oder erzeugen. Das könnte so aussehen (CoffeeScript):

Code: Alles auswählen

#!/usr/bin/env coffee

Number::divides = (n) -> n % this == 0


class PrimeGenerator
    constructor: ->
        @primes = []
        @candidate = 1
        @next = @_firstNext

    candidateIsPrime: ->
        for prime in @primes
            if prime.divides(@candidate)
                return false
        true

    _next: ->
        loop
            @candidate += 2
            if @candidateIsPrime()
                @primes.push(@candidate)
                return @candidate

    _firstNext: ->
        @next = @_next
        2


factor = (n) ->
    result = []
    primes = new PrimeGenerator()
    while n > 1
        prime = primes.next()
        if prime.divides(n)
            result.push(prime)
            n /= prime while n > 1 and prime.divides(n)
    result


console.log(factor(parseInt(process.argv[2])))

Das könnte man so fast 1:1 in Python umsetzen. Allerdings hat Python eine tolle Syntax um die Klasse durch eine Generatorfunktion zu ersetzen die fast wie die Rückruf-Variante von `primes()` aus der JavaScript-Lösung oben aussieht: die ``yield``-Anweisung.

Code: Alles auswählen

#!/usr/bin/env python
import sys


def iter_primes():
    primes = []
    candidate = 3
    yield 2
    while True:
        if all(candidate % prime != 0 for prime in primes):
            primes.append(candidate)
            yield candidate
        candidate += 2


def iter_factors(number):
    for prime in iter_primes():
        if number == 1:
            return
        if number % prime == 0:
            yield prime
            while number > 1 and number % prime == 0:
                number //= prime


def main():
    if len(sys.argv) < 1:
        print 'usage: {0} number'.format(sys.argv[0])
    else:
        try:
            number = int(sys.argv[1])
        except ValueError:
            print 'Not a valid number:', sys.argv[1]
        else:
            print list(iter_factors(number))


if __name__ == '__main__':
    main()

[snafu]

Um's nochmal deutlich zu sagen: Man benötigt zum Finden von Primfaktoren (wie ich jetzt gelernt habe) definitiv keine `is_prime()`-Funktion. Das Prinzip ist einfach, dass man mit der kleinstmöglichen Zahl als ersten Kandidaten beginnt und dann aufsteigend vorgeht. Immer dann, wenn die zu zerlegende Zahl durch einen Kandidaten teilbar ist, dann kann man sie solange durch den Kandidaten teilen bis sie *nicht* mehr durch diesen Kandidaten teilbar ist. Damit hat man dann auch ausgeschlossen, dass die Zahl noch durch irgendwelche Vielfachen des Kandidaten teilbar ist. Beispiel: Wenn man eine Zahl fortwährend durch 2 teilt, dann wird sie definitiv nicht mehr durch 4, 6, 8, ... teilbar sein. Wichtig dabei ist halt, dass die Ursprungszahl auch tatsächlich geschrumpft wird. Wenn die geschrumpfte Zahl irgendwann nicht mehr glatt durch den Kandidaten teilbar ist, dann probiert man das weitere Schrumpfen der Zahl mit dem nächsten Kandidaten solange bis dieser nicht mehr geht, usw. Man fährt solange fort bis man zu einem Kandidaten kommt, dessen Wert größer ist als der Wert der fortwährend geschrumpften Zahl. Dann ist man fertig und der letzte Kandidat, der noch ein glatter Teiler war (also: derjenige, der *vor* dem zur Abbruchbedingung führenden Kandidaten dran kam), ist der gesuchte größte Primfaktor.

Durch den Vorgang des fortwährenden Schrumpfens spart man sich die quadratische Laufzeit, die man beim Einbau von `is_prime()` hätte, da wie gesagt ein Vielfaches einer Primzahl sofort "sehen" würde, dass es nicht glatt durch die geschrumpfte Zahl teilbar ist. Dies heißt dann automatisch, dass dieses Vielfache keine Primzahl sein kann. Wenn man das einmal verstanden hat, dann kann man sich an entsprechende Optimierungen machen, wie z.B. dem Testen von ausschließlich ungeraden Zahlen (außer der 2 natürlich) oder der Verwendung der Quadratwurzel, um das fortwährende Teilen abkürzen zu können. Ob man dann noch weitere Optimierungen einführen möchte, ist wohl Geschmackssache. Das, was Sirius3 zum Schluss gepostet hatte, ist zwar ganz nett und ich ziehe den Hut vor solchen Kenntnissen, aber wenn man es mit so großen Eingabewerten zu tun bekommt, dass ein solcher doch eher unschöner Algorithmus nötig wird, dann würde ich persönlich eher zu C greifen und den Algo dort implementieren - denn wenn's schon hochoptimiert sein soll, dann richtig.

[Sirius3]

@snafu: durch meine Handoptimierung der Assemblerausgabe einer C-Funktion konnte ich die Anzahl der Befehle nochmals halbieren. Für primitive Algorithmen kann es also durchaus den Aufwand lohnen, in die Tiefen der Hardware hinabzusteigen, obwohl noch nicht daraufhin geprüft habe, ob durch falsches Aligning noch ein paar Taktzyklen verloren gehen.

[snafu]

@Sirius3: Du kannst ja gerne ein Erweiterungsmodul für Python in C schreiben, welches Inline-Assembler-Befehle benutzt, wenn du Spaß dran hast. Gibt es aber vermutlich auch schon in irgendeiner Form. ^^

[Gwunderi]

Um's nochmal deutlich zu sagen: Man benötigt zum Finden von Primfaktoren (wie ich jetzt gelernt habe) definitiv keine `is_prime()`-Funktion. Das Prinzip ist einfach, dass man mit der kleinstmöglichen Zahl als ersten Kandidaten beginnt und dann aufsteigend vorgeht. Immer dann, wenn die zu zerlegende Zahl durch einen Kandidaten teilbar ist, dann kann man sie solange durch den Kandidaten teilen bis sie *nicht* mehr durch diesen Kandidaten teilbar ist. Damit hat man dann auch ausgeschlossen, dass die Zahl noch durch irgendwelche Vielfachen des Kandidaten teilbar ist. Beispiel: Wenn man eine Zahl fortwährend durch 2 teilt, dann wird sie definitiv nicht mehr durch 4, 6, 8, ... teilbar sein. Wichtig dabei ist halt, dass die Ursprungszahl auch tatsächlich geschrumpft wird. Wenn die geschrumpfte Zahl irgendwann nicht mehr glatt durch den Kandidaten teilbar ist, dann probiert man das weitere Schrumpfen der Zahl mit dem nächsten Kandidaten solange bis dieser nicht mehr geht, usw. Man fährt solange fort bis man zu einem Kandidaten kommt, dessen Wert größer ist als der Wert der fortwährend geschrumpften Zahl. Dann ist man fertig und der letzte Kandidat, der noch ein glatter Teiler war (also: derjenige, der *vor* dem zur Abbruchbedingung führenden Kandidaten dran kam), ist der gesuchte größte Primfaktor.

Genau so isses (habe auch ich jetzt beim Pröbeln richtig begriffen).

Praktisch ist es aber nicht immer so einfach? Was ist z.B., wenn der erste Kandidat die Zahl selber ist, also n eine Primzahl ist? oder sie nur zwei Primfaktoren, z.B. 2 und eine Riesenzahl, hat? Hatte beim Pröbeln mit dem Programm von Sirius eine solche Primzahl gefunden, ich glaube eine 12-stellige (oder war sie noch höher?).

Verstehe das Programm von Sirius (noch) nicht, hatte in der Zwischenzeit auch keine Zeit, aber sie hat diese Primzahl im Nu herausgegeben. Möglich, dass es für noch sehr viel höhere Zahlen nicht mehr viel taugt : ) ... Überhaupt verstehe ich die meisten Programme hier nicht, es fehlt mir einfach noch das Grundwissen.

So wie ich mich kenne, werde ich mich aber morgen wieder ans Pröbeln machen ... oder soll ich es vorläufig belassen?

Dein Hauptproblem, abgesehen von den vielen Sonderfällen die da unnötigerweise unterschieden werden, ist dass Du `n` nicht verkleinerst wenn Du einen Faktor gefunden hast. Dadurch testest Du deutlich mehr Teiler als nötig.

Und Du erzeugst dadurch auch mehr Primzahlen als nötig. Das kann man auf das Nötigste begrenzen in dem man das Programm so schreibt, dass jede gefundene Primzahl sofort nach dem sie gefunden wurde, verwendet wird um `n` zu verkleinern.

Ja, siehe oben. Die vielen Sonderfälle: ja, man kann das Programm bestimmt noch verkürzen, und all die Zwischenresultate hatte ich eigentlich für mich eingebaut, gehören nicht in ein fertiges Programm ... : ) Bin auch noch nicht dazu gekommen, Dein obiges Python-Programm zu testen, geschweige denn, es zu verstehen versuchen ...

Grüsslein, Gwunderi