Euler 001

Publié le 20/12/16

Soit N dans \mathbb{N}.
Écrire une fonction donnant la somme des entiers de [1,N[ divisibles par 3 ou 5.
Remarque: l’énoncé original du « Project Euler » se limite à N=1000.
Le résultat est alors 233168.
  1. Première solution

  2. Deuxième solution

  3. Troisième solution
    On peut simplifier en appliquant directement sum sur le générateur (à aucun moment on ne forme la liste des valeurs).

  4. Quatrième solution

  5. Cinquième solution

  6. Sixième solution

    Notons S(d,N) la somme des entiers de [1,\ldots,N[ qui sont divisibles par d.
    Ces entiers sont les n=kd, où 1\le k\le m, où m=\Big\lfloor{\displaystyle\frac{N-1}{d}}\Big\rfloor, donc S(d,N)=\displaystyle\frac{m(m+1)}2\,d.
    On calcule donc la somme des éléments de [1,\ldots,N[ qui sont divisibles par 3, on y ajoute la somme de ceux qui sont divisibles par 5, mais il y retrancher la somme de ceux qui sont divisibles par 15 (sinon ceux-ci seraient comptés deux fois!).
    Remarque: la complexité est ici indépendante de l’entier N qui borne l’intervalle de la recherche. Dans les solutions précédentes, la complexité est linéaire en N car on forme (ou on parcourt) la liste des entiers de 1 à N-1.