[résolu] Aide pour resoudre exercice: Recherche Nombres Premiers "Eratosthène"

Bonjour, g un exercice que je trouve une difficulté a résoudre, il propose de chercher tous les entiers premiers inferieurs ou egaux a N donne et ceci en utilisant la méthode suivant a:
- ecrire ts les entiers naturel compris entre 2 et N
- 2 n'est pas enlevé de cette liste, donc il est premier; maintenant on enleve de la liste tous les multiples de 2.
- le plus petit nombre non enleve etant 3:il est premier; maintenant enlever de la liste tous les multiples de 3.
- et ainsi de suite
merci

lire(n)

pour i de 1 a n-1 faire
t(i)<--i+1
fin pour
nbr_premier(t,n,1)
fin prog principale

0)def proc nbr_premier( t:tab; n:entier; i:entier)
1)si i si t(i <> 0 ) then
ecrire (t(i),'premier')
pour j de i+1 a n-1 faire
si t(j) mod t(i)=0 alors
t(j)<-- 0
fin si
fin pour
PROC nbr_premiers(t,n,i+1)
fin si
fin si
2) fin procedure






c'est une solution mais chui pas sur si elle est correcte a toi de la verifier et de l'ameliorer

Merciii pour la solution, g exécuté ce code et ca marche, je vais essayer d'apporter une petite modification qui consiste a: a chaque fois que un entier represente un multiple de l'entier en question on décale le tableau vers la gauche de telle sorte que le tableau final ne contiendra que les entiers premiers compris entre 2 et n puis afficher ce tableau resultat.

sasouki a écrit:Bonjour, g un exercice que je trouve une difficulté a résoudre, il propose de chercher tous les entiers premiers inferieurs ou egaux a N donne et ceci en utilisant la méthode suivant a:
- ecrire ts les entiers naturel compris entre 2 et N
- 2 n'est pas enlevé de cette liste, donc il est premier; maintenant on enleve de la liste tous les multiples de 2.
- le plus petit nombre non enleve etant 3:il est premier; maintenant enlever de la liste tous les multiples de 3.
- et ainsi de suite
merci

C'est ce qu'on appelle la méthode du Crible d'Ératosthène. Voir ce lien pour plus d'information.



Je te propose la solution suivante écrite en Pascal:

Code:

program Crible_Eratosthene;
uses wincrt;

Type
  TAB = array[1..1000] of integer;

Procedure Saisie(var n: integer);
begin

  repeat
    write('Saisir N: ');
    readln(n);
  until (n in [2..100])
 
end;

Procedure Affichage(n: integer; T: TAB);
var
  i: integer;
begin
  for i:=1 to n do
  begin
    if (T[i]>0) then
        writeln(T[i]);
  end; 
end;

Procedure Premiers(n: integer; var T: TAB);
var
  i,j: integer;
begin
  for i:=1 to n do
      T[i] := i;

  for i:=2 to n-1 do
      for j:=i+1 to n do
          if ((T[i]>0) and (T[j]>0) and (T[j] mod T[i]=0)) then
            T[j] := -1;
end;

var
  N: integer;
  T: TAB;

Begin

  Saisie(N);
  Premiers(N,T);
  Affichage(N,T)

end.


Merci infiniment et l'animation est excellente