Problème #3 du project Euler

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

L’algorithme du sieve of Eratosthenes

Copyright : Fraser Mummery

Eratosthenes of Cyrene est un mathématicien, géographe, poète, astronome et théoricien de la musique né en Grèce antique. Il a été un grand penseur, à l’origine notamment des premières cartes représentatives du monde, tel que celui-ci était connu à l’époque. C’est à lui que l’on doit entre autres, le jour bissextile (le 29 février), de nombreuses découvertes en matière de géographie dont une approximation raisonnable du diamètre de la Terre, et le fameux crible d’Ératosthène.

Cet algorithme est une manière efficace de retrouver tous les nombres premiers. Celui-ci consiste à tester la primalité des nombres de 2 à n selon la méthode décrite ci-après.

L’algorithme du crible d’Ératosthène décrypté

Considérons une liste de nombres entiers de 2 à n, 2 étant le premier des nombres premiers. On récupère tous les multiples de 2 appartenant à cette liste, et on les marque comme étant non premiers : par définition, tout multiple de 2 est divisible par 2. Le multiple d’un nombre ne peut donc pas être premier.

On cherche ensuite le premier des nombres supérieurs à 2 n’étant pas marqué dans la liste, et on répète la précédente instruction, à savoir marquer comme étant non premiers tous les multiples de ce nombre. On récupère ainsi le nombre 3 et on parcourt ses multiples afin de les marquer comme nombre non premier.

Chacune de ces opérations est répétée jusqu’à ce que l’on arrive à la limite de cette liste, le nombre n. Quand l’algorithme se termine, tous les nombres qui n’auront pas été marqués dans la liste constituent la séquence de nombres premiers inférieurs à n.

Animation of the Sieve of Eratosthenes

Chacun des nombres restants une fois l’algorithme terminé est nécessairement nombre premier, car tous les multiples des nombres inférieurs auront déjà été marqués. Il se peut, par ailleurs, qu’un multiple ait déjà été marqué : c’est le cas du nombre 6 par exemple. Ce nombre est marqué originellement comme étant non premier car il est multiple de 2. 6 étant également multiple de 3, il pourrait éventuellement être marqué une deuxième fois.

Une évolution de l’algorithme énoncé ci-dessus serait de commencer à marquer tous les multiples d’un nombre premier à partir du carré de celui-ci, car tous les plus petits multiples de celui-ci auront d’ores-et-déjà été marqués. Cela signifie aussi que l’algorithme peut se terminer lorsque le carré d’un des nombres premiers trouvés est supérieurs à n.

…en JavaScript

Ci-dessous, une des écritures possibles de cet algorithme en JavaScript, permettant d’obtenir tous les nombres premiers inférieurs à n. detectprimes est un tableau de n booléens. On attribue la valeur true à l’ensemble des nombres de 2 à n, 0 et 1 ne faisant pas partie de cet ensemble sont initialisés avec la valeur false.

Une boucle for est mise en place, avec une limite de √n. À chaque nouvelle itération sur le tableau de n nombres, on vérifie si p est premier – si p est égal à true – et seulement à cette condition, on évalue tous les multiples de p supérieurs au carré de p, afin de les marquer à false, comme étant non premiers donc.

Il ne reste ensuite qu’à parcourir les éléments du tableau detectprimes, afin de récupérer tous les nombres premiers inférieurs à n.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      for(var j = p*p; j < n; j += p)
        detectprimes[j] = false;
    }
  }

  // Get all the prime numbers
  for (var i = 0; i < n; i++)
    if(detectprimes[i]) primes.push(i);
  return primes;
}

Pour vérifier le bon comportement de la fonction que je vous propose, voici une représentation textuelle de l'image qui schématise l'algorithme proposé par Ératosthène.

En exécutant le code présent ci-après, vous pourrez mieux appréhender le déroulement du crible d'Ératosthène. Cette nouvelle version, proposant des commentaires, à l'aide de console.log est bien évidemment moins efficace en terme de performance, mais vous permettra de suivre chacun des tests effectués à chacune des itérations de la boucle.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();
  console.log('I want to know which numbers below ' + n + ' are primes.');

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      console.log(p + ' is a prime, let\'s mark all its multiples below ' + n + '.');
      for(var j = p*p; j < n; j += p){
        console.log(j + ' is a multiple of '+p+', so ' + j + ' is not a prime.');
        detectprimes[j] = false;
      }
    }else{
      console.log(p + ' is not a prime, so the loop continues.');     
    }
  }
  console.log(p + ' is not smaller than ' + Math.sqrt(n) + ': end of the loop.');

  // Get all the prime numbers
  var _text = 'The primes below ' + n + ' are: ';
  for (var k = 0; k < n; k++) {
    if (detectprimes[k]) {
      primes.push(k);
      if (primes.length == 1) _text += k;
      else _text += ', ' + k;
    }
  }
  console.info(_text + '.');
  return primes;
}
eratosthenes(121);

Vous aurez dans votre console la sortie suivante :

I want to know which numbers below 121 are primes.

2 is a prime, let’s mark all its multiples below 121.
4 is a multiple of 2, so 4 is not a prime.
6 is a multiple of 2, so 6 is not a prime.
8 is a multiple of 2, so 8 is not a prime.
10 is a multiple of 2, so 10 is not a prime.
12 is a multiple of 2, so 12 is not a prime.
14 is a multiple of 2, so 14 is not a prime.
16 is a multiple of 2, so 16 is not a prime.
18 is a multiple of 2, so 18 is not a prime.
20 is a multiple of 2, so 20 is not a prime.
22 is a multiple of 2, so 22 is not a prime.
24 is a multiple of 2, so 24 is not a prime.
26 is a multiple of 2, so 26 is not a prime.
28 is a multiple of 2, so 28 is not a prime.
30 is a multiple of 2, so 30 is not a prime.
32 is a multiple of 2, so 32 is not a prime.
34 is a multiple of 2, so 34 is not a prime.
36 is a multiple of 2, so 36 is not a prime.
38 is a multiple of 2, so 38 is not a prime.
40 is a multiple of 2, so 40 is not a prime.
42 is a multiple of 2, so 42 is not a prime.
44 is a multiple of 2, so 44 is not a prime.
46 is a multiple of 2, so 46 is not a prime.
48 is a multiple of 2, so 48 is not a prime.
50 is a multiple of 2, so 50 is not a prime.
52 is a multiple of 2, so 52 is not a prime.
54 is a multiple of 2, so 54 is not a prime.
56 is a multiple of 2, so 56 is not a prime.
58 is a multiple of 2, so 58 is not a prime.
60 is a multiple of 2, so 60 is not a prime.
62 is a multiple of 2, so 62 is not a prime.
64 is a multiple of 2, so 64 is not a prime.
66 is a multiple of 2, so 66 is not a prime.
68 is a multiple of 2, so 68 is not a prime.
70 is a multiple of 2, so 70 is not a prime.
72 is a multiple of 2, so 72 is not a prime.
74 is a multiple of 2, so 74 is not a prime.
76 is a multiple of 2, so 76 is not a prime.
78 is a multiple of 2, so 78 is not a prime.
80 is a multiple of 2, so 80 is not a prime.
82 is a multiple of 2, so 82 is not a prime.
84 is a multiple of 2, so 84 is not a prime.
86 is a multiple of 2, so 86 is not a prime.
88 is a multiple of 2, so 88 is not a prime.
90 is a multiple of 2, so 90 is not a prime.
92 is a multiple of 2, so 92 is not a prime.
94 is a multiple of 2, so 94 is not a prime.
96 is a multiple of 2, so 96 is not a prime.
98 is a multiple of 2, so 98 is not a prime.
100 is a multiple of 2, so 100 is not a prime.
102 is a multiple of 2, so 102 is not a prime.
104 is a multiple of 2, so 104 is not a prime.
106 is a multiple of 2, so 106 is not a prime.
108 is a multiple of 2, so 108 is not a prime.
110 is a multiple of 2, so 110 is not a prime.
112 is a multiple of 2, so 112 is not a prime.
114 is a multiple of 2, so 114 is not a prime.
116 is a multiple of 2, so 116 is not a prime.
118 is a multiple of 2, so 118 is not a prime.
120 is a multiple of 2, so 120 is not a prime.

3 is a prime, let’s mark all its multiples below 121.
9 is a multiple of 3, so 9 is not a prime.
12 is a multiple of 3, so 12 is not a prime.
15 is a multiple of 3, so 15 is not a prime.
18 is a multiple of 3, so 18 is not a prime.
21 is a multiple of 3, so 21 is not a prime.
24 is a multiple of 3, so 24 is not a prime.
27 is a multiple of 3, so 27 is not a prime.
30 is a multiple of 3, so 30 is not a prime.
33 is a multiple of 3, so 33 is not a prime.
36 is a multiple of 3, so 36 is not a prime.
39 is a multiple of 3, so 39 is not a prime.
42 is a multiple of 3, so 42 is not a prime.
45 is a multiple of 3, so 45 is not a prime.
48 is a multiple of 3, so 48 is not a prime.
51 is a multiple of 3, so 51 is not a prime.
54 is a multiple of 3, so 54 is not a prime.
57 is a multiple of 3, so 57 is not a prime.
60 is a multiple of 3, so 60 is not a prime.
63 is a multiple of 3, so 63 is not a prime.
66 is a multiple of 3, so 66 is not a prime.
69 is a multiple of 3, so 69 is not a prime.
72 is a multiple of 3, so 72 is not a prime.
75 is a multiple of 3, so 75 is not a prime.
78 is a multiple of 3, so 78 is not a prime.
81 is a multiple of 3, so 81 is not a prime.
84 is a multiple of 3, so 84 is not a prime.
87 is a multiple of 3, so 87 is not a prime.
90 is a multiple of 3, so 90 is not a prime.
93 is a multiple of 3, so 93 is not a prime.
96 is a multiple of 3, so 96 is not a prime.
99 is a multiple of 3, so 99 is not a prime.
102 is a multiple of 3, so 102 is not a prime.
105 is a multiple of 3, so 105 is not a prime.
108 is a multiple of 3, so 108 is not a prime.
111 is a multiple of 3, so 111 is not a prime.
114 is a multiple of 3, so 114 is not a prime.
117 is a multiple of 3, so 117 is not a prime.
120 is a multiple of 3, so 120 is not a prime.

4 is not a prime, so the loop continues.

5 is a prime, let’s mark all its multiples below 121
25 is a multiple of 5, so 25 is not a prime.
30 is a multiple of 5, so 30 is not a prime.
35 is a multiple of 5, so 35 is not a prime.
40 is a multiple of 5, so 40 is not a prime.
45 is a multiple of 5, so 45 is not a prime.
50 is a multiple of 5, so 50 is not a prime.
55 is a multiple of 5, so 55 is not a prime.
60 is a multiple of 5, so 60 is not a prime.
65 is a multiple of 5, so 65 is not a prime.
70 is a multiple of 5, so 70 is not a prime.
75 is a multiple of 5, so 75 is not a prime.
80 is a multiple of 5, so 80 is not a prime.
85 is a multiple of 5, so 85 is not a prime.

90 is a multiple of 5, so 90 is not a prime.
95 is a multiple of 5, so 95 is not a prime.
100 is a multiple of 5, so 100 is not a prime.
105 is a multiple of 5, so 105 is not a prime.
110 is a multiple of 5, so 110 is not a prime.
115 is a multiple of 5, so 115 is not a prime.
120 is a multiple of 5, so 120 is not a prime.

6 is not a prime, so the loop continues.

7 is a prime, let’s mark all its multiples below 121.
49 is a multiple of 7, so 49 is not a prime.
56 is a multiple of 7, so 56 is not a prime.
63 is a multiple of 7, so 63 is not a prime.
70 is a multiple of 7, so 70 is not a prime.
77 is a multiple of 7, so 77 is not a prime.
84 is a multiple of 7, so 84 is not a prime.
91 is a multiple of 7, so 91 is not a prime.
98 is a multiple of 7, so 98 is not a prime.
105 is a multiple of 7, so 105 is not a prime.
112 is a multiple of 7, so 112 is not a prime.
119 is a multiple of 7, so 119 is not a prime.

8 is not a prime, so the loop continues.

9 is not a prime, so the loop continues.

10 is not a prime, so the loop continues.

11 is not smaller than 11, end of the loop.

The primes below 121 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.

Pour aller plus loin : bien d'autres algorithmes proposent de récupérer l'ensemble des nombres premiers, d'autres mêmes jugés encore plus rapides d'exécution que le crible d'Ératosthène comme le sieve of Atkins ou encore le sieve of Sundaram, pour ne citer qu'eux.

Mais le sieve of Eratosthenes que je vous propose aujourd'hui est l'un des plus simples à écrire, et il a la particularité de dater du IIIème siècle avant Jésus-Christ, une prouesse mathématique pour l'époque !

Problème #2 du project Euler

Copyright : Michæl Paukner

« Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. »

Afin de résoudre ce problème du projet Euler, il est important, dans un premier temps, de se consacrer à l’appréhension de ce que ce sont les séquences Fibonacci. En mathématiques, la séquence Fibonacci se définit comme une séquence dans laquelle chaque nombre est obtenu en effectuant la somme des deux termes précédents.

La formule mathématique associée est donc la suivante : F(n) = F(n-1) + F(n-2) avec F(0) = 0 et F(1) = 1. On appelle F(0) et F(1) les termes initiaux de cette suite logique, ceux qui permettent d’en déduire les nombres suivants. Les nombres Fibonacci constituent la séquence A000045 sur The On-line Encyclopedia of Integer Sequences. Ci-dessous sont représentés les vingt premiers termes de la séquence Fibonacci.

F(0) F(1) F(2) F(3) F(4)
0 1 1 2 3
F(5) F(6) F(7) F(8) F(9)
5 8 13 21 34
F(10) F(11) F(12) F(13) F(14)
55 89 144 233 377
F(15) F(16) F(17) F(18) F(19)
610 987 1 597 2 584 4 181

L’énoncé du problème #2 du projet Euler nous propose de trouver la somme de toutes les valeurs paires n’excédant pas 4 000 000. Il s’agit donc de considérer la séquence Fibonacci, de telle sorte qu’à chaque nouveau terme étant pair, celui-ci est ajouté à une variable sum, dont la valeur ne cessera d’augmenter que lorsque l’on aura atteint la limite proposée, égale à 4 000 000.

Les deux termes initiaux de la séquence Fibonacci sont représentés ci-dessous par les variables x et y respectivement égales à 0 et à 1. Ces variables possèdent une valeur croissante dans le temps à la condition que la variable y, représentant systématiquement le deuxième terme à un instant t, ne dépasse jamais la limite imposée. Une variable intermédiaire temp calcule le troisième terme créé à partir de la somme de x et y. x, premier terme de la séquence à un instant t, devient alors égal à y, qui lui-même prend la valeur de temp. À chaque nouvelle itération, on ajoute à la variable sum la valeur de la variable y si celle-ci est paire.

function problem2(){
  var limit = 4000000,
      sum = 0,
      x = 0,
      y = 1;

  while(y < limit){
    if(y%2==0) sum += y;
    var temp = x + y;
    x = y;
    y = temp;
  }
  return sum;
}

problem2();

En clair, lors de la première itération de cette boucle, on a : x = F(0) et y = F(1). temp représente d'abord F(2) et est donc égal à F(0) + F(1), soit x +y. x prend ensuite la valeur de y donc x = F(1) = 1 ; y prend la valeur de temp donc y = F(2) = 1.

Lors de la deuxième itération de la boucle, on a donc : x = F(1) et y = F(2). temp va représenter F(3), et donc être égal à F(1) + F(2), soit x +y. x prend ensuite la valeur de y donc x = F(2) = 1 ; y prend la valeur de temp donc y = F(3) = 2.

À la troisième itération de cette boucle, y étant égal à 2, chiffre pair, sera ajouté à sum. Et ainsi de suite, jusqu'à ce que y dépasse 4 000 000.

La fonction présente ci-dessus s'exécute en 0.12 milliseconde.

Problème #1 du Project Euler

Copyright : Pedro Ribeiro Simões

Avez-vous déjà entendu parler du fameux Project Euler ? Non, jamais ?! Vraiment ? Et pourtant, il rapproche plus de 440 000 utilisateurs dans le monde entier !

La popularité du projet Euler ne cesse de croître au fil des années auprès notamment des développeurs, des étudiants des filières scientifiques, ou simplement des adultes passionnés en mathématiques. Et pour cause…

Le project Euler

Le projet Euler commence le 5 octobre 2001 en tant que rubrique sur le site MathsChallenge.net. Cette initiative née du clavier de Colin Hughes est aussi une manière de rendre hommage au travail du mathématicien et physicien d’origine suisse Leonhard Euler.

Il consiste en une multitude de problèmes plus ou moins faciles à résoudre : il en existe plus de 500 aujourd’hui. L’objectif de tout développeur qui accepte de relever le défi est de proposer un algorithme simple et efficace en termes de performance pour parvenir à une réponse, correcte bien évidemment. Et vous verrez que plus vous avancerez dans le compte des problèmes proposés, plus difficile il sera pour vous de développer des mini programmes ultra rapides pour obtenir les solutions.

Bon, ça y’est : vous êtes convaincus de tenter l’expérience ?! Je vous propose ci-dessous la résolution du premier problème de cette longue liste du projet Euler. Le code que vous retrouverez ci-dessous est ma propre interprétation de ces énoncés en JavaScript. Mais libre à vous de me proposer votre manière de les résoudre, avec d’autres langages, ou d’améliorer mon code en le rendant plus rapide par exemple. J’accepte volontiers vos remarques ou suggestions !

Le problème #1

« If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000. »

Le problème 1 est probablement le plus simple à résoudre du projet Euler. Il s’agit de déterminer la somme des nombres inférieurs à 1000 qui sont des multiples de 3 ou de 5. Par définition, si le nombre b est un multiple du nombre a, cela signifie que a est un diviseur du nombre b. Et que donc, la division b/a n’admet pas de reste.

D’après cette formule, la solution à implémenter paraît évidente. Et qu’importe le langage choisi, les programmes écrits pour parvenir à la solution de ce problème ont tendance à se ressembler. Pour ma part, j’ai donc créé en JavaScript une boucle for testant successivement tous les nombres inférieurs à 1000 et vérifiant si le reste de la division de ce nombre par 3 ou de ce nombre par 5 est nul. Si l’une de ces conditions est vraie, alors j’ajoute ce nombre à la somme totale.

function problem1(){
  var sum = 0;
  for (var i = 3; i < 1000; i++){
    if(i%3==0 || i%5==0) sum += i;
  }
  return sum;
}
problem1();

Ce petit programme s'exécute en 17 millisecondes sur mon ordinateur. Ça vous semble convenable, n'est-ce-pas ? Il existe pourtant une façon bien plus efficace de parvenir à la solution de ce problème !

Vous pouvez décider de calculer de manière indépendante la somme des nombres divisibles par 3 inférieurs à 1000 et la somme des nombres divisibles par 5 inférieurs également à 1000. De l'addition de ces deux sommes, il suffit de retirer la somme des nombres divisibles par 15, pour ne pas comptabiliser en double les multiples de 15, 15 représentant le produit de 3 par 5.

Observons de près ces deux sommes : si on additionne tous les multiples de 3 inférieurs à 1000, on a : 3 + 6 + 9 + ... + 999 soit le produit 3 x (1 + 2 + 3 + ... + 333). Et si nous additionnons tous les multiples de 5 inférieurs à 1000, nous obtenons : 5 + 10 + 15 + ... + 995 soit 5 x (1 + 2 + 3 + ... + 199).

Sachant que la somme de tous les nombres de 1 à n est égale à la formule n*(n+1)/2, il ne manque plus qu'à déterminer le plus grand des multiples du nombre souhaité en dessous de 1000 pour pouvoir effectuer le bon produit. Pour le chiffre 5, le plus grand des multiples en dessous de 1000 est 995, soit l'équivalent de la soustraction de ce nombre par le reste de la division 999/5. Je divise ensuite ce nombre par 5, pour obtenir le fameux 199. La somme des nombres de 1 à 199 est égale à (199x200)/2 soit 19 900. Je multiple ce nombre par 5 est le tour est joué !

function sumdivisibleby(x){
  var target = 999 - (999%x),
      n = target/x;
  return x*(n*(n+1))/2;
}

function problem1(){
  return sumdivisibleby(3) + sumdivisibleby(5) - sumdivisibleby(15);
}

Ce nouveau programme s'exécute en 6 millisecondes ! La différence peut vous sembler infime... Mais testez à nouveau ces deux fonctions, cette fois, pour trouver les multiples de 3 et 5 en dessous de 10 000 000 : la deuxième fonction s'exécute, chez moi, en 5 millisecondes, tandis que la première possède une durée d'exécution de 85.04 millisecondes. Une différence de plus en plus conséquente !

Comme vous le démontre l'exemple précédent, les possibilités sont grandes, et tous les moyens sont bons pour arriver au résultat tant convoité d'un problème. Certains algorithmes seront par contre plus efficaces que d'autres, et le projet Euler est une bonne manière de réfléchir aux enjeux de la performance lors du développement d'une fonctionnalité, et ce, quelque soit le langage que vous utilisez au quotidien.