Discussion :

[sali2801]

SALU TOUT LE MONDE
j'ai un exercice d'ALGO j'ai essayé de trouver la solution mais je suis pas sûre.


EXO
Construire l'algorithme qui nous donne les N premiers nombres premiers?


Ma solution

ALGORITHME nmb_premier;
Var N, i: entier

DEBUT

Lire (N);
Pour i allant de 1 à N faire
DPOUR
Si ( N Mod i ) =/= 0
DSI
ecrire (i)
FSI
FPOUR
FIN.

Veuillez me corriger

[ToTo13]

Bonjour,

cet algorithme est faux
- aller de 1 à N ne donne pas les N premiers nombres premiers.
- N % i =/= 0 permet de savoir si N est divisible par i. Si i varie de 2 à N-1 est qu'aucune valeur de i ne divise N, alors dans ce cas N est premier.
Corrigez donc en utilisant ma deuxième remarque.

Pour avoir les N nombres premier, on utilise souvent le crible d'Eratostène.

[sali2801]

Bonjour,

cet algorithme est faux
- aller de 1 à N ne donne pas les N premiers nombres premiers.
- N % i =/= 0 permet de savoir si N est divisible par i. Si i varie de 2 à N-1 est qu'aucune valeur de i ne divise N, alors dans ce cas N est premier.
Corrigez donc en utilisant ma deuxième remarque.

Pour avoir les N nombres premier, on utilise souvent le crible d'Eratostène.

Merci mais j'ai pas bien compri ta 2 eme remarque?

[Graffito]

Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est l'ancêtre du crible d'Atkin qui est plus rapide mais plus complexe.

source : wikipedia

[Obsidian]

Merci mais j'ai pas bien compri ta 2 eme remarque?

Il faut chercher un peu toi-même, surtout avant de faire remonter ton message (ce qui est proscrit sur ce forum en l'absence d'éléments supplémentaires). Cherche Crible d'Ératosthène sur Wikipédia, tu le trouves immédiatement. Le crible d'Ératosthène est une méthode connue depuis l'antiquité et qui relève du simple bon sens : pour trouver les nombres premiers, on élimine les autres (les multiples).

Tu commences à 0, puis tu sautes les cases de 2 en 2, en les rayant à chaque fois. Tu élimines ainsi tous les nombres pairs. Ensuite, tu recommences en partant de zéro et tu sautes les cases de trois en trois, toujours en les rayant. Tu élimines ainsi tous les nombres multiples de trois. Et ainsi de suite en sautant de 4 en 4, 5 en 5, etc.

Toutes les cases que tu n'as pas rayées entre le zéro et la première case où tu sautes sont forcément des nombres premiers.