Größter Primfaktor von 600851475143

Code-Stücke können hier veröffentlicht werden.
Antworten
mrUnkreativ
User
Beiträge: 3
Registriert: Donnerstag 21. August 2014, 16:41

Sonntag 24. August 2014, 18:30

Es geht um Aufgabe 3 von projekteuler.net

Also ich hab mir folgendes Ausgedacht:

Code: Alles auswählen

zahl = 600851475143
var = 600851475142

def uII():
    if var%2 == 0:
        return False
    else:
        return True

    
def uIII_IX():
    quer = sum([int(i) for i in str(var)])
    if (quer%3 == 0) and (quer%9 == 0):
        return False
    else:
        return True


def uV():
    if var%5 == 0:
        return False
    else:
        return True


def uVII():
    if var%7 == 0:
        return False
    else:
        return True

def teiler():
    if zahl%var == 0:
        return True
    else:
        return False


while True:
    if (uII() == True) and(uIII_IX() == True) and (uV() == True)\
    and (uVII() == True):
        print var

        if teiler() == True:
            print "Lösung: " + var
            break
        
    if uII() == False :
        var = var - 1
    else:
        var = var - 2
Es sollen praktisch alle Zahlen vor "zahl" durchgegangen werden, geprüft werden ob sie Primzahlen sind und ob sie ein Teiler von "zahl" sind.

Das Zeigen der Primzahlen, die nicht in Frage kommen, soll nur veranschaulichen, dass das Programm arbeitet.

Jetzt zu meiner Frage:
Das ganze dauert nun ziemlich. Habt Ihr vielleicht eine Idee wie man das ganze schneller und eleganter lösen kann?
Die Arbeitsweise ist mir Nacht um 3 eingefallen. Also vielleicht deswegen und wegen mangelnder Erfahrung nicht ganz ausgereift :D


Freue mich auf eure Antworten!
Lg Max
BlackJack

Sonntag 24. August 2014, 19:07

@mrUnkreativ: Erstmal zum Quelltext selber: Da kommen deutlich zu viele `True`- und `False`-Literale drin vor. Bei einem Vergleich kommt doch schon ein Wahrheitswert heraus. Da kann man dann auch gleich *diesen* zurück geben statt noch ein ``if``/``else`` drum herum zu basteln wo dann in den Zweigen nur `True` oder `False` zurückgegeben wird.

Und vergleichen sollte man gegen literale `True`/`False`-Werte auch nicht, denn auch da kommt ja auch wieder `True` oder `False` heraus, und dafür hätte man auch den anderen Wert der Vergleichsoperation hernehmen können, oder seine Negation, falls man auf das Gegenteil prüfen möchte.

Auf Teilbarkeit durch zwei braucht man nicht prüfen wenn man nur ungerade Teiler prüft (ausser der 2).

Du sagst Du prüfst alle Zahlen ob sie Primzahl und Teiler sind, das machst Du aber gar nicht. Die paar Tests die Du machst, sind nicht ausreichend um zu zeigen das `var` eine Primzahl ist. Es gibt ja durchaus Primzahlen jenseits von der 7, das heisst die Zahl die Du so findest kann trotzdem noch durch eine andere Zahl teilbar sein.

Der Witz bei solchen Challenges ist es ja eigentlich selber auf die Idee zu kommen. Denn wenn man die erst einmal hat, dann ist es meistens ganz einfach. Ich würde jedenfalls von ”unten” Anfangen zu testen durch welche Zahlen geteilt werden kann, ausser der 2 nur die ungeraden testen, und das Teilen dann auch *machen*!
mrUnkreativ
User
Beiträge: 3
Registriert: Donnerstag 21. August 2014, 16:41

Sonntag 24. August 2014, 19:40

Code: Alles auswählen

zahl = 600851475143
teiler = 3

while True:
    if zahl%teiler == 0:
        zahl = zahl/teiler
        print teiler

    teiler = teiler + 2

    if teiler > zahl:
        print "Finish"
        break

Wow... das war wirklich peinlich einfach ._. :roll:

Danke :)
BlackJack

Sonntag 24. August 2014, 20:11

So kann man das mit einer ``for``-Schleife ausdrücken:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
from __future__ import print_function
from itertools import count


def main():
    zahl = 600851475143
    for teiler in count(3, 2):
        if teiler >= zahl:
            break
        if zahl % teiler == 0:
            zahl //= teiler
    print(teiler)


if __name__ == '__main__':
    main()
Antworten