« The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ? »
Le troisième problème du projet Euler reprend les notions mathématiques de nombres premiers et de facteurs premiers. Un nombre premier est un nombre entier supérieur à 1 qui n’a pour diviseurs que 1 et lui-même.
Les facteurs premiers d’un nombre entier, quant à eux, sont l’ensemble des nombres premiers qui divisent entièrement cet entier. Par exemple, les facteurs premiers du nombre 70 sont 2, 5 et 7. Comme le décrit l’énoncé de ce problème, les facteurs premiers de 13 195 sont 5, 7, 13 et 29.
La factorisation en nombres premiers d’un entier peut également être exprimée à l’aide de puissances. En guise d’illustration, le nombre 300 peut se décomposer de la manière suivante : 2 x 2 x 3 x 5 x 5. Pour simplifier cette écriture, le carré est souvent utilisé : 2² x 3 x 5².
Algorithme de la solution
Pour trouver le plus grand des facteurs premiers d’un nombre entier x
, on considère comme probable diviseur de ce nombre tous les entiers supérieurs à 1, 2 étant le premier des nombres premiers.
Si l’entier considéré divise entièrement x
, on divise successivement x
par ce nombre, jusqu’à que ce nombre ne soit plus un facteur de x
. Cette opération garantit la primalité du nombre considéré car tous les plus petits facteurs de x
auront d’ores-et-déjà été traités.
Une première écriture de cet algorithme donnerait le résultat suivant. La fonction obtenue s’exécute en 12.57 millisecondes sur mon ordinateur.
function problem3(){ var x = 600851475143, largest = 1, k = 2; while(x > 1){ // If k is a factor of x if(x % k == 0){ largest = k; x = x / k; while(x % k == 0) x = x / k; } k++; } // Give the largest prime factor of x return largest; }
Une première évolution de ce code serait de traiter le nombre 2 à part, car 2 est le seul nombre premier de valeur paire. Cela nous permet par la suite d’utiliser la même boucle, en incrémentant de 2 chaque potentiel candidat à être facteur. On testera donc de manière successive les nombres 3, 5, 7, etc..
Ce nouvel algorithme s’exécute en 3.22 millisecondes sur mon ordinateur.
function problem3(){ var x = 600851475143, largest = 1, k = 3; // If 2 is a factor of x, we treat it separately... if(x % 2 == 0){ x = x / 2; largest = 2; while(x % 2 == 0) x = x / 2; } // ... so we can increase factor with 2 every iteration while(x > 1){ if(x % k == 0){ largest = k; x = x / k; while(x % k == 0) x = x / k; } k += 2; } // Give the largest prime factor of x return largest; }
Il est encore possible d’améliorer l’efficacité de cette fonction en considérant que chaque entier x
ne peut avoir au maximum qu’un seul nombre premier supérieur à sa racine carrée.
Après avoir divisé de manière successive un des nombres premiers trouvés, on calcule la racine carrée de la valeur restante de x
. Si le facteur considéré est supérieur à la racine carrée de x
, alors la valeur restante de x
est le plus des grands des nombres premiers de x
.
Cette nouvelle version s’exécute cette fois en 1.84 milliseconde sur mon ordinateur.
function problem3(){ var x = 600851475143, largest = 1, k = 3; // If 2 is a factor of x, we treat it separately... if(x % 2 == 0){ x = x / 2; largest = 2; while(x % 2 == 0) x = x / 2; } // ... so we can increase factor with 2 every iteration // This loop runs only if k is not bigger than the square // root of the remaining x while(x > 1 && k<= Math.sqrt(x)){ if(x % k == 0){ largest = k; x = x / k; while(x % k == 0) x = x / k; } k += 2; } // Give the largest prime factor of x if(x == 1) return largest; else return x; }