ProjectEuler.net : Problème 1

Le premier problème est le suivant: 

Si on liste tous les nombres naturels en dessous de 10 qui sont multiple de 3 et 5, on obtient 3,5,6,9 et la somme de ces multiples est égale à 23. Trouver la somme de tous les multiples de 3 et 5 en dessous de 1000.

Instinctivement, on est porté à utiliser une boucle for avec 1000 itérations, et à chaque fois on vérifie si la variable de contrôle, soit i, est égale à un multiple de 3 ou 5 à l'aide du modulo. Ce n'est pas une mauvaise façon de le faire, mais mathématiquement ce n'est pas satisfaisant.

 #include <stdio.h>  
 main () {  
 int result, threes, fives, i = 0;  
      for (i = 1; i < 1000; i++){  
           threes = i % 3;  
           fives = i % 5;  
           if (threes == 0 || fives == 0)   
                result = result + i;  
      }  
 printf("%d\n", result);  
 printf("threes : %d\n", threes);  
 printf("fives : %d\n", fives);  
 }  

Premièrement, on sait que:

x(x + 1)	= 1+2+...+x
2

Le problème peut-être interprété de la façon suivante:

(3+6+9+...+999) + (5+10+15+...+995)

Si on sort les facteurs communs...

3(1+2+3+...+333) + 5(1+2+3+...+199)

EUREKA!! On peut donc utiliser la formule qu'on a définit plus haut. On définit une fonction SumDivisibleBy(int multiple) et la valeur de n est calculé de la façon suivante :

n = 999/multiple

On applique cette formule utilisant le multiple 3 et le multiple 5 et on fait la somme des 2 valeurs retournées. Cependant, notre idée ne tient pas compte des nombres entre 1 et 1000 qui sont À LA FOIS multiples de 3 et de 5, donc des multiples de 15, il suffit de les supprimer de la somme. Et voilà!

 #include <stdio.h>  
 int target = 999;  
 int SumDivisibleBy(multiple) {  
      int x = target/multiple;  
 return multiple*x*(x+1)/2;  
 }  
 main (){  
      int result = SumDivisibleBy(3) + SumDivisibleBy (5) - SumDivisibleBy(15);  
      printf("La somme de tous les multiples de 3 et 5 contenu dans 1000 est : %d\n", result);  
 }