Problème #3 du project Euler

Threes connect
geir tønnessen

« 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é 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 chez moi !

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

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *