Simulation

#1 introduction

Les nombres premiers, excepté le nombre 2, sont tous impairs. On peut donc partir des nombres impairs (ce faisant, on supprime tous les multiples de 2).

Le nombre 9 est-il premier ? Il faut vérifier qu'il ne se trouve pas dans la table de ses diviseurs premiers (3, 5 ou 7) ? Comme on l'a vu précédemment, il suffit de le comparer aux nombres premiers inférieurs ou égaux à sa racine carrée. La racine carrée de 9 étant 3, on va donc le comparer uniquement à la table de 3. 

                    3 x 1 = 3
                    3 + 3 = 6
                    6 + 3 = 9
Pour éviter les nombres pairs, on part de 3 (impair) et on ajoute 6 à chaque fois (6 = 3 x 2). De cette façon, on saute les nombres pairs, inutiles. 

                    3 x 1 = 3
                    3 + 6 = 9
9 se trouve dans la table de 3, donc il n'est pas premier.

A priori, la difficulté pourrait-être de calculer la racine carrée du nombre. Mais on peut trouver, sur le web, des vidéos expliquant comment rechercher manuellement la racine carrée d'un nombre.

Prenons un autre exemple : 139. Est-il premier ?

Sa racine carrée se calcule comme suit : 

            1 39| 1 1, ...
                |____________________
                | 1 du dividende = . x . ? 
                | 1 = 1 x 1
           -1   |  
          = 0   | 1 + 1 = 2
            0 39| 39 = 2. x . ?
                | 39 = 21 x 1 = 21 
            - 21|    
            = 18| ... calcul des décimales,
                |     inutile ici.
La partie entière de la racine carrée de 139 est 11.

Si on devait rechercher si 139 est premier, il suffirait de le comparer aux tables des diviseurs premiers inférieurs ou égaux à sa racine carrée (ici 11) soit aux tables de 3, 7 et 11. En l'espèce, le nombre 139 est premier.

La table de 5 est inutile car les nombres (excepté 5) se terminant par 5 ne peuvent pas être premiers.

#2 Calcul des nombres premiers des 100 premiers nombres

On va construire un tableau :

Combien de colonne pour les tables de multiplication ? On recherche sur les 100 premiers nombres donc racine carrée de 100 = 10 => les colonnes des tables inférieures ou égales à 10 c'est-à-dire 3 et 7.

On commence les calculs à partir du carré des diviseurs premiers : pour 3 => 32 = 9, pour 7 => 72 = 49.

Dans la colonne de la table de 3, les multiples se suivent de 6 en 6 (3 x 2). De même, dans la colonne des 7, les multiples se suivent de 14 en 14 (7 x 2). Il suffit donc de trouver un seul nombre dans la colonne, et on trouve tous les autres en ajoutant ou retranchant 6 pour la table de 3 ou 14 pour la table de 7.

Table 3 Table 7     Primes
2 2
3 3
5 5
7 7
9 32 = 9 -
 
11 11
13 13
15 9 + 6 = 15 -
17 17
19 19
 
 
21 15 + 6 = 21 -
23 23
25 -
27 21 + 6 = 27 -
29 29
 
 
31 31
33 27 + 6 = 33 -
35 -
37 37
39 33 + 6 = 39 -
 
 
41 41
43 43
45 39 + 6 = 45 -
47 47
49 72 = 49 -
Table 3 Table 7     Primes
51 45 + 6 = 51 -
53 53
55 -
57 51 + 6 = 57 -
59 59
 
61 61
63 57 + 6 = 63 49 + 14 = 63 -
65 -
67 67
69 63 + 6 = 69 -
 
 
71 71
73 73
75 69 + 6 = 75 -
77 63 + 14 = 77 -
79 79
 
 
81 75 + 6 = 81 -
83 83
85 -
87 81 + 6 = 87 -
89 89
 
 
91 77 + 14 = 91 -
93 87 + 6 = 93 -
95 -
97 97
99 93 + 6 = 99 -

De cette façon empirique, il a été possible de trouver les 25 nombres premiers qui se trouvent dans la 1ère centaine : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].

#3 Recherche de la primalité d'un nombre (et recherche du nombre premier suivant)

# 3.1 Calcul avec le nombre '409'

A l'aide de la technique vue au chapitre précédent, essayons de rechercher si 409 est un nombre premier et si oui quel est le nombre premier suivant.

Pour ce faire, reconstituons le tableau pour la quatrième centaine (de 400 à 499).

Avant, calculons la racine carrée de 409 : 

            4 09| 2 0, ...
                |________
            -4  | 4 = 2 x 2
            = 0 |
                | 2+2 = 4
            0 09| 4.x. 
                | 40x0 = 0

La partie entière de la racine carrée est 20. On doit donc construire le tableau avec les colonnes des tables de multiplication de 3, 7, 11, 13, 17 et 19.

[En fait, pour reconstruire toute la centaine, il faudrait calculer la racine carrée du dernier nombre de la centaine soit ici 499. Mais ici, cela ne change rien car la racine carrée de 499 - soit 22,3383 - est inférieure à 23 donc on reste sur la table de multiplication 19 au maximum.]

Commençons par la table de 3, la plus facile : il faut que la somme des chiffres qui compose le nombre soit divisible par 3. 401 donne 5, 403 donne 7 et on trouve 405 qui donne 9. Donc 405 est à mettre dans la colonne de 3. Puis on remplit la colonne tous les 6 cases suivantes : 405+6=411, 411+6=417, 417+6=423, etc.

Et Maintenant, on fait la même chose avec 7 et les autres colonnes :

. 400 / 7 :
. 40 / 7 = 5 reste 5
. '5' + '0' = 50 => 50 / 7 = 7 environ donc '5' + '7' = '57'.
. 7 x 57 = 399 => + 14 = 413.
. Puis, on remplit la colonne des 7 tous les 14 => 413 + 14 = 427 ...

t. 3 t. 7 t. 11 t. 13 t. 17 t. 19   Primes
401 -
403 -
405 405 -
407 -
409 -
411 411 -
413 413 -
415 -
417 417 -
419 -
421 -
423 423 -
425 -
427 427 -
429 429 -
431 -
433 -
435 435 -
437 -
439 -
441 441 441 -
443 -
445 -
447 447 -
449
451 -
453 453 -
455 455 -
457 -
459 459 -
461 -
463 -
465 465 -
467 -
469 469 -
471 471 -
473 -
475 -
477 477 -
479 -
481 -
483 483 483 -
485 -
487 -
489 489 -
491 -
493 -
495 495 -
497 497 -
499 -

. 400/11 : 40/11 = 3 puis 70/11 = 6 => 36. 11x36 = 396 (pair) + 11 (pour avoir impair) = 407. Puis on remplit de 22 en 22 (11 x 2).
. 400/13 ; 40/13=3 => 30/13=2 => 32. 13x32=416 (pair) + 13 = 429 ...+26.. +26...
. 400/17 : 40/17=2 60/17=3 => 23. => 17x23=391 + 34 = 425 ... +34...
. 400/19 : 40/19=2 => 20/19=1 => 19x21=399 => +(19x2=38) = 437 ... +38=475 ... +38=513

Une fois les colonnes des tables de multiplication remplies, il ne reste plus qu'à remplir la dernière colonne.

t. 3 t. 7 t. 11 t. 13 t. 17 t. 19   Primes
401 401
403 403 -
405 405 -
407 407 -
409 409
411 411 -
413 413 -
415 -
417 417 -
419 419
421 421
423 423 -
425 425 -
427 427 -
429 429 429 429 -
431 431
433 433
435 435 -
437 437 -
439 439
441 441 441 -
443 443
445 -
447 447 -
449 449
451 451 -
453 453 -
455 455 455 -
457 457
459 459 459 -
461 461
463 463
465 465 -
467 467
469 469 -
471 471
473 473 -
475 475 -
477 477 -
479 479
481 481 -
483 483 483 -
485 -
487 487
489 489 -
491 491
493 493 -
495 495 495 -
497 497 -
499 499

En lisant le tableau, on voit que 409 est premier et que le prochain nombre premier sera 419.

# 3.2 Calcul avec le nombre '919'

La partie entière de la racine carrée de 919 est 30 : 
            9 19| 3 0, ...
                |________
            -9  | 3 x 3 = 9
            = 0 |
                | 3+3 = 6
            0 19| 6.x. 
                | 6 0 x 0 = 0
Les tables des colonnes sont : 3, 7, 11, 13, 17, 19, 23 et 29.

Mais pour calculer toute la centaine, il faut calculer la racine du dernier nombre soit ici 999. Sa racine carrée est 31. Il faut ajouter la colonne 31.

. 90/7=12 => reste 6 => 60/7=8. '12'+'8' = 128 => 128 x 7 = 896 (pair) + 7 = 903
. 90/11=8 => 20/11=1 => 81. x11=891+22=913
. 90/13=6 => 120/13=9 => 69. x13=897+26=923
. 90/17=5 => 50/17=3 => 53. x17=901
. 90/19=4 => 140/19=7 => 47. x19=893 + (19x2) = 931
. 90/23=3 => 210/23=9 => 39. x23=897 + (2x23) = 943
. 90/29=3 => 30/29=1 => 31. x29=899 + (2x29) = 957
. 90/31=2 => 280/31=9 => 29. x31=899 + (2x31) = 961

3 7 11 13 17 19 23 29 31   Primes
901 901 -
903 903 903 -
905 -
907 907
909 909 -
911 911
913 913 -
915 915 -
917 917 -
919 919
921 921 -
923 923 -
925 -
927 927 -
929 929
931 931 931 -
933 933 -
935 935 935 -
937 937
939 939 -
941 941
943 943 -
945 945 945 -
947 947
949 949 -
951 951 -
953 953
955 -
957 957 957 957 -
959 959 -
961 961 -
963 963 -
965 -
967 967
969 969 969 969 -
971 971
973 973 -
975 975 975 -
977 977
979 979 -
981 981 -
983 983
985 -
987 987 987 -
989 989 -
991 991
993 993 -
995 -
997 997
999 999 -

Le nombre 919 est premier et le prochain nombre premier sera 929.

On doit maintenant créer le programme pour simuler, exactement comme le ferait un être humain avec une feuille de papier et un crayon, le process expliqué plus haut : programme de Simulation .