Étude d’un algorithme

Dans un premier temps on initialise les variables (n, p et compagnie...) à leurs valeurs de départ.
Ensuite, on insère une boucle qui ordonne au programme de répéter la partie.

si reste (n,a) . reste (n,b) = 0 alors
 p=1
sinon
 a=6k-1 ; b=6k+1 ;k=k+1
fin

tant que a+p*l est inférieur ou égal à l (=racine de n)...

Cette boucle, parlons-en, il s’agit en fait d’une condition qui en fonction de la valeur du reste de la division de n par a et par b va modifier la valeur de nos variables et par le biais de ces modifications nous permettre de sortir de la boucle et également autre chose que nous allons voir ensuite...

Donc, si le reste de la division de n par a est nul (donc si a|n) ET si b|n aussi, p=1

Dans le cas contraire, on modifie les valeurs de a, b et k conformément à ce qui est écrit dans l’algorithme

Pas si sûr ...... un produit est nul ........

1-On vérifie que a+p*n <= l

 a+p*n
=2+0*324
=0 > l

Cette condition est vraie, on fait donc un tour de boucle

2-On vérifie que a|n et que b|n

324/2 = 162, reste 0
324/3 = 108, reste 0

Cette condition est donc vraie, donc p = 1.

3-A la fin de la boucle on revérifie si a+p*n <= 0 pour savoir si on repart pour un tour de boucle

 a+p*n
=2+1*324
=972 > l (comme l = 18)

Cette condition est fausse, par conséquent on sort de la boucle.

et p=0, a=2, k=1 sont 3 constantes.

pourtant, si a|n OU si b|n

or reste(n, a)*reste(n, b)=0

alors p=1 <---- alors qu’au début j’ai dit que p constante (p=0) du coup I’m lost :s

Je vais essayer d’expliquer pourquoi, je ne garantis pas le résultat :

Au départ, on demande au programme de vérifier si a + p * n < l
Or, dans la première boucle, p = 0.
Si a < l, alors a + p * n < l, quel que soit n...

Donc, le programme continue :

On lui demande de vérifier si le produit des restes des divisions de n par a et b est nul, ce qui signifierait qu’au moins l’un des deux l’est, et donc que n est divisible soit par a, soit par b.

Si c’est le cas, alors on change la valeur de p en 1, et le programme affiche "Non", car le nombre n n’est pas premier...
On sort également de la boucle, puisque désormais a + p * n > l.

Si ce n’est pas le cas, alors la boucle continue. On recommence, en changeant les variables a, b, et k :
k se voit ajouter une unité, a vaut alors 6k-1, b 6k+1.

Or, on a vérifié dans la première boucle que n n’était pas divisible par 2 et 3.
n ne peut donc s’écrire ni 6m, ni 6m+2 (= 2(3m+1)) , ni 6m+3 (= 3(2m+1)), ni 6m+4 (= 2(3m+2))
Il ne reste que deux possibilités : n s’écrit 6m+1, ou 6m+5 (ce qui, modulo 6, revient à 6m-1).

Ces deux dernières possibilités, nous les testons justement toutes en donnant à a la valeur de 6k-1 et b la valeur de 6k+1, et en augmentant la valeur de k de 1 à chaque boucle.

Si n s’écrit 6m+1 ou 6m-1, nous le saurons donc forcément en calculant à chaque fois le produit des restes des divisions de n par a et b. Si ce produit est nul, alors un des restes est nul, impliquant que n est divisible par a ou b.

Le programme va boucler en cherchant tous les diviseurs possibles de n, de la forme 6m+1 ou 6m-1.
S’il en trouve un, il sortira de la boucle de la même façon que dans la première boucle, et affichera "Non".

S’il n’en trouve pas, il va continuer de tester tous les suivants. Mais il finira par sortir de la boucle, car il arrivera un moment, en augmentant continuellement la valeur de a, que ce dernier devienne supérieur à l, impliquant ainsi que a + p * n > l (car p=0). Et le nombre n n’ayant aucun diviseur autre que 1 et lui-même, il sera premier, et le programme affichera "Oui".