Problèmes de nombres premiers

Dans une recherche rapide, je viens de faire, le moyen le plus rapide de faire correspondre un nombre consiste à utiliser la méthode de la courbe elliptique.

Vous pouvez essayer de jeter votre numéro à cette démo: http://www.alpertron.com .ar / ecm.htm .

Si cela vous convaincu, vous pouvez essayer de voler le code (ce n'est pas amusant, ils vous offrent un lien!) Ou lire la théorie de celui-ci ailleurs. Il y a un article Wikipedia à ce sujet ici: http://fr.wikipedia.org/wiki/lenstra_elliptic_curve_factorization Mais je suis trop stupide pour le comprendre. Heureusement, c'est votre problème, pas le mien! :)

La chose avec le projet Euler est qu'il ya généralement une méthode de force brute évidente à faire le problème, qui prendra à peu près jamais. Comme les questions deviennent plus difficiles, vous aurez besoin de mettre en œuvre des solutions intelligentes.

Une façon de résoudre ce problème est d'utiliser une boucle qui trouve toujours le facteur d'un plus petit nombre (entier positif). Lorsque le plus petit facteur d'un nombre est ce nombre, alors vous avez trouvé le plus grand facteur premier p>

Description détaillée Algorithme: p>

Vous pouvez le faire en gardant trois variables: p>

Le nombre que vous essayez de facteur (A) Un magasin courant de diviseur (B) Un plus grand magasin diviseur (C) p>

Dans un premier temps, que (A) le nombre qui vous intéresse - dans ce cas, il est 600851475143. Ensuite nous (B) soit 2. Avoir un test qui examine si (A) est divisible par (B). Si elle est divisible, diviser (A) (B), remise à zéro (B) à 2, et revenir à vérifier si (A) est divisible par (B). Sinon, si (A) est non divisible par (B), incrément (B) par +1, puis vérifier si (A) est divisible par (B). Exécutez la boucle jusqu'à ce que (A) est 1. Le (3) vous revenez sera le plus grand diviseur premier de 600.851.475.143 p>

Il existe de nombreuses façons, vous pouvez le rendre plus efficace -. Au lieu de incrémenter à l'entier , vous pouvez augmenter le nombre entier suivant nécessairement le premier, et au lieu de garder un plus grand magasin de diviseur, vous pouvez simplement retourner le nombre actuel lorsque son seul diviseur est lui-même. Cependant, l'algorithme I décrit ci-dessus fonctionne en quelques secondes quel que soit p>

La mise en œuvre en Python est comme suit: -. P>

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()