6eme 5eme 4eme 3eme
Sommaire Liens Atelier Maths Forum

Test de primalité

programme JavaScript

Crible d'Erathostène

programme JavaScript

Les nombres premiers

Les nombres premiers ont fasciné des générations de mathématiciens, mais de quoi s'agit-il ?

Un entier naturel est premier s'il n'admet que deux diviseurs : 1 et lui-même.

1 n'est pas premier, c'est une convention.

2, 3, 5, 7, 11 sont premiers.

A partir de cette simple définition, on peut trouver (et prouver) quantité de propriétés sur ces nombres, par exemple :

Certains résultats ne sont toujours pas démontrés, par exemple la conjecture de Goldbach (1690-1764) : Il affirme en 1742, sans le démontrer, que tout entier pair supérieur à deux est la somme de deux nombres premiers.

Ainsi, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 7 + 5, 14 = 7 + 7 ...

 

Comment savoir si un entier est premier ?

Soit N un entier naturel. Une façon de faire est de dresser la liste des nombres premiers en éliminant tout d'abord les multiples de 2, puis de 3, puis de 5 (les multiples de 4 ont déjà été éliminés comme multiples de deux), etc. C'est le crible d'Erathostène.

Une autre façon de faire pourrait être de tester la divisibilité de N par tous les entiers naturels qui lui sont inférieurs ... Pas très élégant et cela demande de nombreux calculs pour peu que N soit assez grand.

Ici nous allons "diminuer" le nombre des calculs en remarquant que tout entier naturel peut s'écrire sous la forme 6a, 6a+1, 6a+2, 6a+3, 6a+4, 6a+5 pour un certain a entier relatif :

a = 0 : 6a = 0 ; 6a+1 = 1 ; 6a+2 = 2 ; 6a+3 = 3 ; 6a+4 = 4; 6a+5 = 5

a=1 : 6a = 6 ; 6a+1 = 7 ; 6a+2 = 8 ; 6a+3 = 9 ; 6a+4 = 10; 6a+5 = 11

......................

On peut chercher si N est divisible par l'un de ces six nombres (en prenant a = 0, a = 1, ...).

Or, 6a = 2*3*a, c'est un multiple de 2 et de 3, par conséquent, si N est divisible par 6a, il est aussi divisible par 2 et par 3.

6a+2 = 2*(3a+1), si N est divisible par 6a+2, il est aussi divisible par 2.

6a+3 = 3*(2a+1), si N est divisible par 6a+3, il est aussi divisible par 3.

6a+4 = 2*(3a+2), si N est divisible par 6a+4, il est aussi divisible par 2.

Ainsi, si N n'est pas divisible par 2 ou 3 (ce qu'il est facile de vérifier avec les critères de divisibilité), il n'y a plus qu'à vérifier qu'il ne soit pas divisible par 6a+1 ou 6a+5 pour un certain a.

En pratique on peut s'arrêter lorsque 6a+5 est inférieur ou égal à la racine carré de N.


Test de primalité (Progamme JavaScript) :

N =

Crible d'Erathostène :

Il permet de dresser la liste des nombres premiers inférieurs ou égaux à N en éliminant successivement les multiples de 2 autres que 2, ceux de 3 autres que 3, ...etc.

Une fois éliminés tous les multiples de i, 2 <= i <= k, le plus petit entier p restant est premier, sinon il aurait un diviseur compris entre 2 et k, ce qui est impossible puisqu'on a éliminé tous leurs multiples.

Il faut ensuite éliminer les multiples de p en commençant par p2, les autres multiples de p : kp avec 2 <= k <= p ont été éliminés comme multiples de k.

Programme JavaScript :

N =



Document made with Nvu C. Grospellier