Plus grand facteur premier d’un nombre

En fait, il existe plusieurs moyens plus efficaces de trouver des facteurs de grand nombre (pour les plus petits, la division d’essais fonctionne raisonnablement bien).

Une méthode qui est très rapide si le nombre d’entrée a deux facteurs très proches de sa racine carrée est la factorisation de Fermat . Il utilise l’identité N = (a + b) (a – b) = a ^ 2 – b ^ 2 et est facile à comprendre et à mettre en œuvre. Malheureusement, ce n’est pas très rapide en général.

Le tamis quadratique est la méthode la plus connue pour factoriser des nombres allant jusqu’à 100 chiffres. En prime, une partie de l’algorithme se fait facilement avec un parallel processing.

Un autre algorithme dont j’ai entendu parler est l’algorithme Rho de Pollard . Ce n’est pas aussi efficace que le Quadratic Sieve en général, mais semble être plus facile à mettre en œuvre.

Une fois que vous avez décidé de diviser un nombre en deux facteurs, voici l’algorithme le plus rapide auquel je puisse penser pour trouver le facteur premier le plus important d’un nombre:

Créez une queue prioritaire qui stocke initialement le numéro lui-même. À chaque itération, vous supprimez le nombre le plus élevé de la queue et tentez de le diviser en deux facteurs (ne permettant pas à l’un de ces facteurs, bien sûr). Si cette étape échoue, le nombre est premier et vous avez votre réponse! Sinon, vous ajoutez les deux facteurs dans la queue et répétez.

Voici le meilleur algorithme que je connaisse (en Python)

 def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 return factors pfs = prime_factors(1000) largest_prime_factor = max(pfs) # The largest element in the prime factor list 

La méthode ci-dessus s’exécute dans O(n) dans le pire des cas (lorsque l’entrée est un nombre premier).

MODIFIER:
Ci-dessous la version O(sqrt(n)) , comme suggéré dans le commentaire. Voici le code, une fois de plus.

 def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 if d*d > n: if n > 1: factors.append(n) break return factors pfs = prime_factors(1000) largest_prime_factor = max(pfs) # The largest element in the prime factor list 

Ma réponse est basée sur Triptych , mais améliore beaucoup sur elle. Il est basé sur le fait qu’au-delà de 2 et 3, tous les nombres premiers sont de la forme 6n-1 ou 6n + 1.

 var largestPrimeFactor; if(n mod 2 == 0) { largestPrimeFactor = 2; n = n / 2 while(n mod 2 == 0); } if(n mod 3 == 0) { largestPrimeFactor = 3; n = n / 3 while(n mod 3 == 0); } multOfSix = 6; while(multOfSix - 1 <= n) { if(n mod (multOfSix - 1) == 0) { largestPrimeFactor = multOfSix - 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } if(n mod (multOfSix + 1) == 0) { largestPrimeFactor = multOfSix + 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } multOfSix += 6; } 

J'ai récemment écrit un article de blog expliquant comment cet algorithme fonctionne.

Je m'aventurerais qu'une méthode dans laquelle il n'y aurait pas besoin de test de primalité (et pas de construction de tamis) serait plus rapide que celle qui les utilise. Si tel est le cas, c'est probablement l'algorithme le plus rapide.

Tous les nombres peuvent être exprimés comme le produit des nombres premiers, par exemple:

 102 = 2 x 3 x 17 712 = 2 x 2 x 2 x 89 

Vous pouvez les trouver simplement en commençant à 2 et en continuant simplement à diviser jusqu’à ce que le résultat ne soit pas un multiple de votre numéro:

 712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1 

en utilisant cette méthode, vous n’avez pas besoin de calculer les nombres premiers: ils seront tous des nombres premiers, car vous avez déjà factorisé le nombre autant que possible avec tous les nombres précédents.

 number = 712; currNum = number; // the value we'll actually be working with for (currFactor in 2 .. number) { while (currNum % currFactor == 0) { // keep on dividing by this number until we can divide no more! currNum = currNum / currFactor // reduce the currNum } if (currNum == 1) return currFactor; // once it hits 1, we're done. } 

  //this method skips unnecessary sortingal divisions and makes //sortingal division more feasible for finding large primes public static void main(Ssortingng[] args) { long n= 1000000000039L; //this is a large prime number long i = 2L; int test = 0; while (n > 1) { while (n % i == 0) { n /= i; } i++; if(i*i > n && n > 1) { System.out.println(n); //prints n if it's prime test = 1; break; } } if (test == 0) System.out.println(i-1); //prints n if it's the largest prime factor } 

Code JavaScript:

 'option ssortingct'; function largestPrimeFactor(val, divisor = 2) { let square = (val) => Math.pow(val, 2); while ((val % divisor) != 0 && square(divisor) <= val) { divisor++; } return square(divisor) <= val ? largestPrimeFactor(val / divisor, divisor) : val; } 

Exemple d'utilisation:

 let result = largestPrimeFactor(600851475143); 

Voici un exemple du code :

La solution la plus simple est une paire de fonctions mutuellement récursives .

La première fonction génère tous les nombres premiers:

1. Commencez par une liste composée de 2 et de tous les nombres impairs supérieurs à 2.
2. Supprimez tous les nombres qui ne sont pas premiers. C’est-à-dire des nombres qui n’ont pas de facteurs premiers (autres qu’eux-mêmes). Voir ci-dessous.

La deuxième fonction renvoie les facteurs premiers d’un nombre donné n dans l’ordre croissant. La stratégie est d’essayer de diviser n par chaque premier qui pourrait être son diviseur:

1. Prenez une liste de tous les nombres premiers en ordre croissant (voir ci-dessus).
2. Soit p un premier dans cette liste, et ps les facteurs premiers de n/p (voir étape 1).
   • Si p carré est supérieur à notre nombre n , alors n est premier. Nous avons fini.
   • Si p divise n , alors p est un facteur premier de n . Les autres facteurs sont ps .
   • Sinon, p n’est pas un facteur premier de n .

Le plus grand facteur premier de n est le dernier nombre donné par la deuxième fonction.

Pour plus de clarté, voici le code de ce qui précède, dans Haskell:

 import Control.Monad -- All the primes primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..] -- Gives the prime factors of its argument primeFactors = factor primes where factor [] n = [] factor xs@(p:ps) n = if p*p > n then [n] else let (d,r) = divMod np in if r == 0 then p : factor xs d else factor ps n -- Gives the largest prime factor of its argument largestFactor = last . primeFactors 

Semblable à la réponse @Triptych mais aussi différente. Dans cet exemple, la liste ou le dictionnaire n’est pas utilisé. Le code est écrit en Ruby

 def largest_prime_factor(number) i = 2 while number > 1 if number % i == 0 number /= i; i -= 1 end i += 1 end return i end largest_prime_factor(600851475143) # => 6857 

 n = abs(number); result = 1; if (n mod 2 == 0) { result = 2; while (n mod 2 = 0) n /= 2; } for(i=3; i