« 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;
}