Comment trouver tous les facteurs premiers dans un entier non signé long long?

Question

J'ai une mission de trouver tous les facteurs premiers d'un nombre ...

Je dois écrire une fonction qui prend un numéro et me dit tous les facteurs premiers du nombre. Par exemple:

• n = 350 facteurs premiers: 2 5 5 7

(je passe à la fonction d'un certain nombre dans la plage 0-18446744073709551615 - le nombre maximum est le plus grand nombre qui correspond à un 64 bits non signé long long nombre entier).

Answer 1

C'est un problème difficile, et l'une des principales raisons pour lesquelles toutes les recherches dans les ordinateurs quantiques. Jetez un oeil à algorithme de Shor . Simple force brute sans optimisations prendrait quelque chose comme 1000 ans, bien que dans ce cas spécifique (entiers 64 bits), vous devriez être en mesure de réduire votre exécution à seulement quelques minutes.

En supposant que vous avez un cas trivial (au plus) un facteur premier, vous pouvez accélérer considérablement en faisant quelque chose comme comptage de 2 et d'essayer chaque numéro (plusieurs fois si cela fonctionne, 12 serait 2, 2, et 3 par exemple). Après avoir trouvé un facteur, réduire votre nombre cible par ce facteur et test si la nouvelle cible est primordiale.

Pour l'accélérer encore, vous pouvez faire le traitement sur plusieurs threads, chacun en charge d'une gamme de diviseurs. Vous pouvez exécuter les testeurs de primalité sur un ou plusieurs fils, fournissant des nombres premiers au fil d'essai afin que vous essayez seulement de diviser par des nombres premiers.

Vous pouvez même rechercher à partir du haut de la bas de gamme, si vous pensez que la personne qui fournit la valeur essaie d'être tricksome, bien que la densité des nombres premiers étant beaucoup plus élevés au bas, ce ne sera probablement pas l'aide .

La principale chose à retenir, cependant, que le plus grand facteur possible de X, en plus pour X lui-même, est la racine carrée de X. Chaque fois que vous trouvez un facteur, le plus grand facteur qui reste possible diminue de manière significative.