One Chapter A Day
ONE CHAPTER A DAY Un chapitre... presque tous les jours !
© Pedro Ribeiro Simões

Problème #1 du Project Euler

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.

Donnez votre avis