Nombre Premier : John Wilson

Bonjour, je lisais "God Created the Integers" par nul autre que, Stephen Hawking, et à la page 594 il fait référence au théorème de Wilson :

L'entier p, qui est plus grand que 1, est un nombre premier, 
si et seulement si, la factoriel de (p + 1) est congruent à -1 modulo p.

(p + 1)! + 1 ≡ 0 mod p

Donc, il existe une façon simple de déterminer si un nombre est premier. Mais il n'existe aucune façon de générer des nombre qui sont premier... Intéressant!

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

Hello World!

Ce blog est créé dans l'intention de conservé certaines notions mathématiques et informatiques que je trouve particulièrement intéressantes. Certes, dans les premiers posts les notions seront assez élémentaires mais je souhaite pouvoir ensuite voir le progrès depuis ce jour. Aussi j'aurai une section dédié aux problèmes du site projecteuler.net, dans laquelle je tenterai d'expliquer mon raisonnement et je citerai quelques faits intéressants.