Problèmes avec les nombres premiers

StackOverflow https://stackoverflow.com/questions/1877255

  •  18-09-2019
  •  | 
  •  

Question

Je suis en train d'écrire un programme pour trouver le plus grand facteur premier d'un très grand nombre, et ont essayé plusieurs méthodes avec des succès. Tous ceux que j'ai trouvé à ce jour ont été incroyablement lent. J'ai eu une pensée, et je me demande si cela est une approche valide: 

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Cette approche prendrait une entrée et serait procédez comme suit:

200 -> 100 -> 50 -> 25 -> 5 (retour)

90 -> 45 -> 15 -> 5 (retour)

Il divise currentNum à plusieurs reprises par le plus petit nombre divisible (le plus souvent 2 ou 3) jusqu'à ce que currentNum lui-même est le premier (il n'y a pas de nombre premier divisibles inférieur au squareRoot de currentNum), et assume c'est le plus grand facteur premier du entrée d'origine.

Est-ce que cela fonctionnera toujours? Sinon, quelqu'un peut me donner un contre?

-

EDIT:. En très grand, je veux dire environ 2 ^ 40, ou 10 ^ 11

Était-ce utile?

La solution

Cela fonctionnera toujours à cause de la Unique Prime factorisation Théorème .

Autres conseils

La méthode fonctionnera, mais sera lente. « Quelle est la taille de vos chiffres? » détermine la méthode à utiliser:

Certes, il fonctionnera (voir la réponse Mark Byers ), mais pour les entrées « très grandes » peut prendre beaucoup trop longtemps. Vous devez noter que votre appel à getLowestDivisiblePrimeNumber() cache une autre boucle, donc cela va à l'O (N ^ 2), et qu'en fonction de ce que vous entendez par « très grand », il peut travailler sur bignums qui sera lente.

Vous pouvez accélérer un peu, en notant que votre algorithme n'a jamais besoin de vérifier des facteurs plus petits que le dernier trouvé.

Vous essayez de trouver les facteurs premiers d'un nombre . Ce que vous proposez fonctionnera, mais sera toujours lent pour un grand nombre .... vous devriez être reconnaissants pour cela, puisque la plupart de la sécurité moderne repose sur ce qui est un problème difficile.

A partir d'une recherche rapide, je viens de le faire, la façon de prendre en compte un nombre connu le plus rapide est en utilisant la méthode Elliptic Curve.

Vous pouvez essayer de lancer votre numéro à cette démo: http://www.alpertron.com .AR / ECM.HTM .

Si vous convainc, vous pouvez essayer soit de voler le code (qui est pas amusant, ils fournissent un lien vers elle!) Ou la lecture sur la théorie de l'ailleurs. Il y a un article de Wikipedia à ce sujet ici: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization mais je suis trop stupide pour comprendre. Heureusement, il 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!

Description détaillée Algorithme:

Vous pouvez le faire en gardant trois variables:

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

Dans un premier temps, soit (A) le numéro que vous êtes intéressé - dans ce cas, il est 600851475143. Ensuite nous (B) soit 2. Avoir une condition qui vérifie si (A) est divisible par (B). Si elle est divisible, diviser (A) (B), à 2, reset (B) 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.

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

La mise en œuvre en Python est la suivante: - 

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()

Exemple: Trouvons le plus grand facteur premier de 105 selon la méthode décrite ci-dessus

.

Soit (A) = 105. (B) = 2 (nous avons toujours commencer par 2), et nous n'avons pas une valeur pour (C) encore.

est (A) divisible par (B)? Non Increment (B) 1: (B) = 3. Est-Is (A) divisible par (B)? Oui. (105/3 = 35). Le plus grand diviseur est trouvé à ce jour 3. Soit (C) = 3. Mise à jour (A) = 35. Remise à zéro (B) = 2.

, est (A) divisible par (B)? Non Increment (B) 1: (B) = 3. Est (A) divisible par (B)? Non Increment (B) 1: (B) = 4. Est (A) divisible par (B)? Non Increment (B) 1: (B) = 5. Est (A) divisible par (B)? Oui. (35/5 = 7). Le plus grand diviseur nous avons trouvé est préalablement stocké dans (C). (C) est actuellement 3. 5 est supérieur à 3, donc nous mettre à jour (C) = 5. Nous mettre à jour (A) = 7. Nous remettons à zéro (B) = 2.

Ensuite, on répète le processus de (A), mais nous allons simplement continuer à incrémenter (B) jusqu'à ce que (B) = (A), parce que 7 est premier et n'a pas d'autres que lui-même diviseurs et 1. (On pourrait déjà arrêter quand (B)> ((a) / 2), vous ne pouvez pas avoir diviseurs entiers plus de la moitié d'un nombre - le plus petit diviseur possible (autre que 1) d'un nombre quelconque est 2)

Donc, à ce moment-là nous revenons (A) = 7.

Essayez de faire quelques-unes d'entre elles à la main, et vous aurez le coup de l'idée

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top