Was ist falsch an meinem code?

[Eliazz]

Hallo alle miteinander
Ich bin ganz neu hier desshalb bitte keine vernichtenden Antworten, ich weiß selber das ich ein ziemlicher noob bin aber wie gesagt ganz neu *lächel*
Jedenfalls: ich bin 13 Jahre alt und habe sehr wenig - wenig Programmiererfahrung, da wir im Informatik Unterricht in der Schule nur Schrott beigebracht bekommen und ich mir alles was ich wissen will selbst anlesen muss. Vor kurzem hat mir ein Bekannter "Projekt Euler" empfohlen. Eine "Rätsel"-Seite, bei der man sich eine Art Textaufgabe stellen muss und dann mit einer Sprache seiner Wahl (oder auch nur durch nachdenken) ein Lösungswert herrausfinden soll den man dann nach Registration eingeben und überprüfen kann. Ist ganz nett und habe auch schon Problem 1 & 2 von 500 gelöst Allerdings stecke ich total bei Problem 3 fest.
--> http://projecteuler.net/problem=3
--> The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Meine Idee war: Eine Liste mit allen Primzahlen von 2-1000 zu erstellen und dann systematisch durch zu probieren.
Ich habe das mal getestet, bekomme aber beim ausführen folgende Fehlermeldung:
-->Traceback (most recent call last):
File "/Users/Elias/Desktop/Pyton/Problem 3.py", line 24, in <module>
e = prime[E]
IndexError: list index out of range
Ich werde euch meinen Code anhängen...
Nicht wundern die Liste sollte noch länger werden, wollte allerdings erst testen und nach Erfolg hinterher die Liste vervolständigen .


-->

Code: Alles auswählen

#What is the largest prime factore of 600851475143?
prime = [2,3,5,7,9,11,13,17,19,23,29,31,37,39,41,43,47,51,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
a = 600851475143
b = prime[-1]
c = prime[-2]
d = prime[-3]
e = prime[-4]
B = 32
C = 31
D = 30
E = 29

while b > -1:
    while c > -1:
        while d > -1:
            while e > -1:
                if b*c*d*e == a:
                    print (a,b,c,d,e,f)
                else:
                    e = prime[E]
                E = E - 1
            E = 29
            e = prime[-4]
            if b*c*d*e == a:
                print (a,b,c,d,e,f)
            else:
                d = prime[D]
            D = D - 1
        D = 30
        d = prime[-3]
        if b*c*d*e == a:
            print (a,b,c,d,e,f)
        else:
            c = prime[C]
        C = C - 1
    C = 31
    c = prime[-2]
    if b*c*d*e == a:
        print (a,b,c,d,e,f)
    else:
        b = prime[B]
    B = B - 1
print('error')

Vielen Dank im Vorraus, ich hoffe ihr seit fündiger als ich ist bestimmt was total banales aber ich komme einfach nicht drauf.
Mfg Elias/zz

[BlackJack]

@Eliazz: An der Stelle enthält `E` anscheinend einen Wert, welcher nicht mehr als Index in die Liste `prime` in Frage kommt. Da `E` nur in einer Zeile verändert wird, und dort jeweils um 1 verringert wird, muss es an der Stelle den Wert -35 angenommen haben.

Code: Alles auswählen

In [2]: len(prime)
Out[2]: 34

In [3]: prime[-33]
Out[3]: 3

In [4]: prime[-34]
Out[4]: 2

In [5]: prime[-35]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
/home/bj/<ipython-input-5-9b8217bcc353> in <module>()
----> 1 prime[-35]

IndexError: list index out of range

In dem Zusammenhang wäre es interessant zu wissen wann die Kleinbuchstaben-Namen `b` bis `e` Deiner Meinung nach Werte kleiner als 0 annehmen können, damit die ``while``-Schleifen enden.

Letztlich ist der Ansatz nicht wirklich passend. Zum einen vom Programmierstil: Der Quelltext enthält viele Codewiederholungen in denen nur die Namen unterschiedlich sind. Zum anderen gehst Du fest von vier Primfaktoren aus. Wie siehst Du *das* denn der Zahl 600851475143 an? Wieso kann es nicht mehr oder nicht weniger Faktoren geben?

Der naheliegenste Ansatz wäre eine Primfaktorzerlegung zu programmieren, und zwar eine für beliebige Zahlen n. (Dein `a`.) Dafür würde man anfangen die Primzahlen bis n zu erzeugen und jedes mal wenn man eine gefunden hat, schauen ob sie ein Faktor ist, und wie oft. Und mit dieser Information kleiner machen. Wenn Du die Zahlen per Hand in diese Liste schreibst, weisst Du doch gar nicht wie lang diese Liste für das gegebene n sein muss. Im Extremfall gibt es zwei Faktoren, die 2 und eine Primzahl die halb so gross wie n ist. Dafür brauchst Du dann eine `prime`-Liste mit allen Primzahlen zwischen 2 und n/2. Ganz so gross wird es für die gegebene Zahl nicht, aber auch da stellt sich IMHO schon die Frage ob Du dafür tatsächlich eine `prime`-Liste manuell erstellen möchtest. Denn *den* Aufwand kannst Du auch haben wenn Du es nur mit Papier und Stift löst. Man möchte ja aber das einem der Rechner die Arbeit erleichtert.

Stichwort zur Primzahlenerzeugung ist das Sieb des Eratosthenes. Es gibt einfachere aber deutlich langsamere und kompliziertere und ein klein wenig schnellere Verfahren. Wobei die komplizierteren in der Regel erst ab richtig grossen Zahlen einen Geschwindigkeitsvorteil bringen. Nichtdeterministische Prüfungen sollte man vielleicht noch erwähnen. Oder auch nicht. Für Zahlen in der Grössenordnung der Aufgabe funktioniert das Sieb von Eratosthenes nämlich gut und ausreichend schnell.

Sprachmittel in Python, die sich zum verwenden anbieten: Funktionen, um das Problem in kleinere Teilprobleme aufzuteilen. Und Generatorfunktionen um Ergebnisse aus vielen Elementen schon während der Berechnung verwenden zu können, sobald ein Element berechnet ist, so dass man nicht warten muss bis das gesamte Ergebnis fertig ist, von dem man am Ende in diesem Fall gar nicht alles benötigt. Das betrifft hier die Primzahlen zwischen 2 und n, beziehungsweise n/2. Man wird nicht alle benötigen, kann im vorraus aber auch nicht sagen bis zu welcher Zahl man tatsächlich berechnen muss für das gegebene `n`.

[Sirius3]

@BlackJack: statt n/2 meintest Du wahrscheinlich Wurzel n. Bei n/2 wäre Dein Sieb nämlich im günstigsten Fall 35GB groß.
Die einfachste Variante, einfach alle Zahlen zu probieren, lässt sich relativ einfach mit einem kleinen Sieb kombinieren. Bei einer Primzahl halbiert sich der Aufwand, bei 3 reduziert er sich um den Faktor 3.8 usw. Das Teilsieb wächst schnell, die Aufwandsreduktion nur sehr langsam. Bei 8 Primzahlen reduziert sich der Aufwand um den Faktor 5.8, man hat aber auch schon eine Folge von 1,6 Millionen Gliedern. Hieran sieht mal deutlich, dass ein volles Sieb sich nicht lohnt, da es ja zusätzlich zum Teilertest noch extra aufgebaut werden muss.

[Eliazz]

Wow danke ihr beiden habt mir ein wenig die Augen geöffnet *lächel* bzw mir kommen gerade 2 Möglichkeiten in den Sinn..
1 Das von dir (blackjack) beschriebene verfahren.
2. Es müsste doch auch Funktionieren, wenn ich meine while Bedingung e > - 1 ( ja irgendwie schwachsinnig..) durch while E >-1 ersetzte (da die liste ja bei 0 beginnt) oder? Ich werde es gleich mal ausprobieren
Mh und ja ursprünglich wollte ich es so lösen wie du es angesprochen hast allerdings habe ich es mir zum Ziel gesetzt nicht zu Googlen und das pPrinzip der Primzahl Erkennung selbst zu finden was mir leider noch nicht gelungen ist... :/
Das mit meinem chaotischen Code tut mir leid, ich hatte noch nicht so die Gelegenheit Python richtig zu lernen und mein Code sieht wohl ziemlich unelegant aus
Eigentlich nur ganz kurz: vielen dank für die raschen antworten, ihr habt mir gut geholfen
Mfg elias/zz

[BlackJack]

@Eliazz: Du kannst es ja erst einmal ganz naiv angehen, den Test ob eine Zahl eine Primzahl ist oder nicht. Von Interesse dafür ist die Modulo-Operation, die in Python mit dem Modulo-Operator ``%`` angeboten wird. Beispiel:

Code: Alles auswählen

In [27]: 10 % 3
Out[27]: 1

In [28]: 18 % 12
Out[28]: 6

Der Operator ergibt den Rest einer ganzzahligen Division.

[Eliazz]

Das wusste ich schon und mir ist auch aufgefallen, das man es so realisieren könnte:
a%n <-- wenn hierbei bei allem was man für n einsetzt 0 herauskommt ist a eine Primzahl.. Aber hier ist ja das Problem... Man muss alles einsetzen.. Jetzt ist mir aber aufgefallen das man sich zu 8 sparen kann, da die Zahl dann auch durch 2 restlos teilbar sein müsste... Ebenso 15 - - > 5... Das hab ich solange fortgeführt bis mir aufgefallen ist das man nur Primzahlen prüfen muss. Aber dann muss ich doch jede Primzahl einsetzten und das sind dann wieder ziemlich viele oder? Also: if a%2 > 0 and a%3>0 and a%7>0 and 11,13,17 usw... Aber dann muss man ja wieder alle Primzahlen eingeben oder???
Mfg elias/zz

[BlackJack]

@Eliazz: Du musst nur Primzahlen einsetzen die kleiner als die zu prüfende Zahl sind. Wenn Du die Zahlen aufsteigend überprüfst, dann hast Du diese Primzahlen ja schon. Du musst also nur *eine* Primzahl zum Start tatsächlich eingeben.

[snafu]

@Eliazz: Du kannst deinen Gedanken mithilfe einer äußeren Schleife und einer inneren Schleife realisieren. Die äußere Schleife durchläuft alle zu prüfenden Zahlen. Die innere Schleife wird in jedem Iterationsschritt dieser äußeren Schleife begonnen (also: pro Zahl ausgeführt). Das Prüfen auf Primzahleigenschaft geschieht erst in der inneren Schleife. Und zwar so, indem du - wie BlackJack schon angedeutet hat - die zu prüfende Zahl mittels Modulo für alle bisher gesammelten Primzahlen "befragst". Wenn für eine Zahl bei der Modulo-Operation Null herauskommt, dann weißt du, dass diese Zahl glatt durch eine der Primzahlen teilbar ist und demnach selbst keine Primzahl sein kann. Du kannst die innere Schleife im Grunde immer dann abbrechen (z.b. durch `break`), wenn klar geworden ist, dass es sich um *keine* Primzahl handelt. Der Programmverlauf würde dann mit dem nächsten Schritt in der äußeren Schleife (d.h. Prüfen der nächsten Zahl auf Primzahleigenschaft) weiter machen.

Du setzt also die Zahl 2 als Primzahl voraus und auf Basis dieser Erkenntnis und des beschriebenen Verfahrens kannst du dann alle weiteren Primzahlen ermitteln. Die Grenze, bei der aufgehört werden soll, wäre nach dieser naiven Annahme dementsprechend die Zahl aus der Aufgabenstellung (also: 600851475143). Gefundene Primzahlen fügst du einfach an eine Liste an, die wie gesagt auch die Grundlage für weitere Prüfungen liefert. Wenn du (oder besser gesagt: dein Programm) dann irgendwann alle Zahlen durch hast, dann ist diese Liste das Endergebnis und du hast einen ersten Schritt zur Lösung der Aufgabe geschafft.

Und ich hoffe, ich habe dir jetzt nicht mehr verraten, als du wissen wolltest... ^^

[Eliazz]

Hallo Liebe beantworter meiner Frage ich habe das Problem nun dank eurer Anregung gelöst
was mir gar nicht klar war: der Primzahl beweis reicht vin 2 -17 für eine ziemlich große genauigkeit, so das es gar nicht soviel arbeit war
hier mein code:

Code: Alles auswählen

#Largest prime factor of 600851475143?
prime_proof = [2,3,5,7,11,13,17,21,23,29,31,37]
p_solutions = []
a = 2
c = 0
while a <= 775147: # 775147 ungefähr Wurzel von 600851475143...
    if a%2 > 0 and a%3 > 0 and a%5 > 0 and a%7 > 0 and a%11 > 0 and a%13 > 0 and a%17 > 0 and a%21 > 0 and a%23 > 0 and a%29 > 0 and a%31 > 0 and a%37 > 0 and 600851475143%a == 0:
        p_solutions.append(a)
    a = a + 1
    c = c + 1
print(p_solutions)
# 7 Möglichkeiten:
# [71, 839, 1471, 6857, 59569, 104441, 486847]
# 6857 is die Richtige :)

Wie man durch einen "run" sehen kann gibt es 7 Möglichkeiten ^^ ich habe die einfachvon oben durchprobiert
naja, was würdet ihr an dieser stelle noch an meinem code verbesser, bzw wie sorge ich für mehr "Effizienz"
vielen dank für alles
Elias/zz

[darktrym]

Ohne den Code im ganzen verstanden zu haben, man könnte sicher mit 3 beginnen und bei jeden Schritt a um 2 erhöhen.

[Sirius3]

@Eliazz: Du brauchst dem Computer nicht Arbeit abzunehmen, die er selber viel besser kann: die Wurzeln einer Zahl ausrechnen, zum Beispiel
Dein Programm sucht alle Teiler der gegebenen Zahl. Gesucht sind aber Primfaktoren. Deshalb findest Du auch Zahlen die nicht gesucht sind. Wenn Du diese dann von Hand noch aussiebst, dann erledigst Du wieder Arbeit, die der Computer eigentlich erledigen sollte. Alle Primfaktoren <= 37 auszuschließen führt auch nicht zu einer allgemeingültigen Lösung.
Programmieren ist meistens nicht, für einen Spezielfall eine Lösung zu finden, sondern ein Problem möglichst allgemein zu lösen. In diesem Fall ist das die Primfaktorzerlegung von beliebigen natürlichen Zahlen. Dafür ist es am besten, wenn Du eine Funktion schreibst, die als Eingabeparameter die zu zerlegende Zahl erhält.
Nun zur Auflösung, warum man nur bis zur Wurzel der Zahl gehen muss: Es gibt maximal einen (Prim)faktor einer Zahl, der größer ist als die Wurzel der Zahl. Diesen findet man einfach dadurch, dass man die Zahl durch alle gefundenen kleineren Primfaktoren teilt. Deine Lösung findet diesen Primfaktor nicht.
Noch ein kleiner Tipp: wenn Du einen Primfaktor p gefunden hast, dann vereinfacht sich das Problem: Du musst die restlichen Faktoren nur noch in einer viel kleineren Zahl a/p finden.

[BlackJack]

Die Idee mit dem Teilen durch bereits bekannte Primzahlen in Pascal (ohne Objekte) umgesetzt:

Code: Alles auswählen

program Factor;

type
  PrimePtr = ^PrimeT;
  PrimeT = record
    prime : Longword;
    next : PrimePtr;
  end;
  PrimeGenT = record
    primes : PrimeT;
    candidate : Longword;
    first : Boolean;
  end;

var primeGen : PrimeGenT;
    prime : Longword;
    n : QWord;
    code : Integer;

procedure InitPrime(prime:PrimePtr; val:Longword); inline;
begin
  prime^.prime := val;
  prime^.next := nil;
end;

procedure InitPrimeGen(); inline;
begin
  InitPrime(@primeGen.primes, 2);
  primeGen.candidate := 3;
  primeGen.first := true;
end;

procedure DestroyPrimeGen();
var p, n:PrimePtr;
begin
  p := primeGen.primes.next;
  while p <> nil do
  begin
    n := p^.next;
    Dispose(p);
    p := n;
  end;
end;

function NextPrime():Longword;
var isPrime:Boolean;
    p, n:PrimePtr;
begin
  if primeGen.first then begin
    NextPrime := 2;
    primeGen.first := false;
  end
  else begin
    repeat
      isPrime := true;
      p := @primeGen.primes;
      n := p;
      while (p <> nil) AND isPrime do
      begin
        if (primeGen.candidate MOD p^.prime) = 0 then isPrime := false;
        n := p;
        p := p^.next;
      end;
      if isPrime then begin
        Assert(p = nil);
        Assert(n^.next = nil);
        NextPrime := primeGen.candidate;
        New(n^.next);
        InitPrime(n^.next, NextPrime);
      end;
      Inc(primeGen.candidate, 2);
    until isPrime;
  end;
end;
    
begin
  if ParamCount < 1 then WriteLn('usage: factor number')
  else begin
    Val(ParamStr(1), n, code);
    if code <> 0 then WriteLn('Not a valid number: ', ParamStr(1))
    else begin    
      InitPrimeGen;
      while n > 1 do
      begin
        prime := NextPrime;
        if (n MOD prime) = 0 then begin
          WriteLn(prime);
          while (n > 1) AND ((n MOD prime) = 0) do n := n DIV prime;
        end;
      end;
      DestroyPrimeGen;
    end;
  end;
end.

Ich frage mich ob Programmieranfänger die nie Pascal schreiben mussten, moderne Sprachen wie Python überhaupt richtig zu schätzen wissen.

[Sirius3]

@BlackJack: man merkt, dass Du schon lange kein Pascal mehr geschrieben hast. Um Bedingungen sind genauso wie in Python keine Klammern nötig und in »NextPrime« böte sich statt der »while«- eine »repeat-until«-Schleife an.

[BlackJack]

@Sirius3: Ob man nun ``while not isprime begin … end;`` oder ``repeat … until isprime;`` schreibt, ist IMHO nahezu egal. Das mit den Klammern weiss ich, die Templates im Editor haben die aber automatisch gesetzt und ich war zu faul die alle löschen. (Ich sollte sie mal aus den Templates löschen und den Autor fragen warum er die da drin hat.)

[darktrym]

Kennen auch die modernen Pascal Varianten(FreePascal) keine Listen oder dyn. Arrays?
Das ist doch der Grund warum der Code so aufgebläht ist.

[Leonidas]

Kennen auch die modernen Pascal Varianten(FreePascal) keine Listen oder dyn. Arrays?

Wer hat denn was von modernen Varianten gesagt? Wenns nicht in Turbo Pascal 7 läuft, dannn ists nicht ernstzunehmen

[BlackJack]

@darktrym: Es gibt dynamische Arrays in FP (und Delphi), aber damit wird es nicht wirklich besser. Jedenfalls nicht wenn man es mit einer Python-Lösung vergleicht:

Code: Alles auswählen

program Factor;

type
  TPrimeGen = record
    primes : array of Longword;
    candidate : Longword;
    first : Boolean;
  end;

var primeGen : TPrimeGen;
    prime : Longword;
    n : QWord;
    code : Integer;

procedure InitPrimeGen(); inline;
begin
  SetLength(primeGen.primes, 1);
  primeGen.primes[0] := 2;
  primeGen.candidate := 3;
  primeGen.first := true;
end;

procedure DestroyPrimeGen();
begin
  SetLength(primeGen.primes, 0);
end;

function NextPrime():Longword;
var isPrime:Boolean;
    i:Integer;
begin
  if primeGen.first then begin
    NextPrime := 2;
    primeGen.first := false;
  end
  else begin
    repeat
      isPrime := true;
      i := Low(primeGen.primes);
      while (i < High(primeGen.primes)) AND isPrime do
      begin
        if (primeGen.candidate MOD primeGen.primes[i]) = 0 then
          isPrime := false;
        Inc(i);
      end;
      if isPrime then begin
        NextPrime := primeGen.candidate;
        SetLength(primeGen.primes, Length(primeGen.primes) + 1);
        primeGen.primes[High(primeGen.primes)] := NextPrime;
      end;
      Inc(primeGen.candidate, 2);
    until isPrime;
  end;
end;
    
begin
  if ParamCount < 1 then WriteLn('usage: factor number')
  else begin
    Val(ParamStr(1), n, code);
    if code <> 0 then WriteLn('Not a valid number: ', ParamStr(1))
    else begin    
      InitPrimeGen;
      while n > 1 do
      begin
        prime := NextPrime;
        if (n MOD prime) = 0 then begin
          WriteLn(prime);
          while (n > 1) AND ((n MOD prime) = 0) do n := n DIV prime;
        end;
      end;
      DestroyPrimeGen;
    end;
  end;
end.

Das dürfte ausserdem ineffizient sein, denn für jetzes ”append” an das Primzahlen-Array muss potentiell der gesamte bisherige Inhalt umkopiert werden.

Wenn man das nicht haben möchte, dann kann man `TList` oder `TObjectList` verwenden. Ersteres verwaltet eine Liste von Zeigern, letzteres eine Liste von Objekten (und damit letztlich auch von Zeigern). Man muss also die Speicherverwaltung für die Zahlen einzeln übernehmen. Zumindest das anfordern von Speicher für jede einzelne Primzahl. Oder man braucht eine Klasse die einzig und alleine eine ganze Zahl kapselt.

[Gwunderi]

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!

@ Eliazz
Vielleicht wäre Dein Programm effizienter, wenn Du in Deiner Liste "prime_proof" die 21 mit der 19 austauschen würdest, oder? (gibt zwar dieselben Lösungen aus, aber nur weil diese zufällig kein Vielfaches von 19 sind).

Habe auch nicht verstanden, warum Du nur bis zur 37 prüfst, und warum von den 7 ausgegebenen Möglichkeiten die 6857 die richtige sein soll. 486847 ist doch auch eine Primzahl und Teiler von 600'851'475'143?

Habe Dein Programm auch etwas abgeändert, so dass es die ganze Zahlenliste auf einmal prüft (anstatt if ... and if ... and if ...). Hat den Vorteil, dass man die Array ändern oder beliebig verlängern kann, ohne in den Bedingungen dieselben Änderungen vornehmen zu müssen. Unten der Code, der die selben Lösungen wie Deine ausgibt (aber eben nicht die grösste Primzahl, die Teiler von n ist):

Code: Alles auswählen

prime_proof = [3,5,7,11,13,17,19,23,29,31,37]
p_solutions = []
a = 3
while a <= 775147: # 775147 ungefähr Wurzel von 600851475143...
    for x in prime_proof:
        if a%x > 0 and 600851475143%a == 0:
            if a not in p_solutions:
                p_solutions.append(a)
    a = a + 2
print(p_solutions)

[Sirius3]

@Gwunderi: 486847 = 71*6857

[Gwunderi]

@Gwunderi: 486847 = 71*6857

Hallo Sirius,

Ja, stimmt. Erst dachte ich, es sei, weil wir nur bis 37 geprüft haben. Also habe ich 71 zur Array hinzugefüht, aber die 486'847 wird trotzdem ausgegeben. Was stimmt da nicht?

In der Schleife wird doch jetzt auch geprüft:
if 486847 % 71 > 0,
d.h. falls 486847 KEIN Vielfaches von 71 ist, dann gib es aus.
Sollte also gar nicht ausgegeben werden?

Wo ist da mein Denkfehler???