Nombre premier

Un nombre entier naturel premier est un nombre qui est divisible seulement par 1 et par lui même. On considère N un entier naturel.

Pour savoir si N est premier, il suffit de tester s’il est divisible par un nombre entier compris entre 2 et la partie entière de sa racine carrée. En effet si N possède un diviseur entier supérieur à sa racine carrée, il en possède aussi un qui est inférieur à sa racine carrée :

Par exemple, 12 est divisible par 4 mais aussi par 3 (12 = 4 x 3). La racine carrée de 12 est environ 3,46.

N désigne le nombre

D désigne le diviseur

R désigne le reste de la division de N par D (opération mod)

<> est utilisé pour le symbole "différent de"

 

Algorithme pour déterminer si un nombre est premier :

Variables : N, D, R entier naturel.

Début

Entrer (N) ;

2 à D

N mod D à R

Tantque (R <> 0) et (D<racine carrée(N)) faire

D+1 à D

N mod D à R

Fintantque

Si R <> 0 alors Afficher (N, "est premier")

sinon Afficher (N, "non premier")

Fin

 

Variante :

Ecrire un algorithme qui affiche les nombres premiers entre 1 et 100 (remarque : 1 n’est pas premier)