Bonjour,
j'aurai besoin qu'on m'aide a écrire un algorithme qui affiche les 10 premiers nombres premiers
 
Merci !

http://membres.lycos.fr/villeminge [...] troduc.htm
 
Edit:  en particulier http://membres.lycos.fr/villeminge [...] atoprg.htm

merci

En fait je n'ai tjrs pas réussi
 
Je dois ecrire un programme qui affiche les 10 premiers nombres premiers parmis les nombres d'une liste, qui les trouve dans la liste
 
   
 
help..

 
on est pas là pour faire tes devoirs.
Montre ce que tu as fait, on t'aidera à corriger.

Nbpremier(x)  
 
   
  Si (x<2)  
  Retourne(FAUX)
  Fin Si
   
  Si (x == 2)  
  Retourne(VRAI)
  Fin si
 
 
  Si ((x % 2) == 0)  
  Retourne(FAUX)
  Fin si
 
 
  i = 3
  TantQue(i*i <= x)
 
 
    Si ((x % i) == 0) Retourne(FAUX);
 
 
    i += 2;
    fin si
 
 
 
  Retourne(VRAI)
 fin tant que

Elle est où ta liste là?

enfin par liste ya pas vrmt de liste, le programme doit juste trouver les 10 premiers nombres premiers (donc avec des tests si, tant que je crois)
personne veut m'aider

j'ai essayé autre chose :
 
Fonction NombresPremiers(NP)
 début
    NP <-lire()
    Si (NP<2)
    Alors écrire("ce nombre n'est pas premier" )
    Fin si
 
..... je n'arrive pas a continuer

méthode la plus simple : suffit de coder comme la définition même d'un nombre premier : pour chaque nombre Y, tu prends son modulo avec tous les nombres X plus petits que lui même (à partir de 1). Si ce modulo vaut 0 lorsque X est différent de 1 et de Y alors, ce nombre n'est pas premier.
C'est aussi simple que cela : deux boucles imbriquées

 
 
Ce serait pas plus rapide de prendre 1 <= X <= Y/2 comme interval ?

 
avec la racine carré de Y c'est encore mieux (et juste)

C'est bon à savoir, juste je ne comprends pas comment la racine carrée permet le test. Va falloir que j'aille chercher la démonstration sur Google.
 
Par contre ça fait utiliser la lib m, c'est pas génant en soi mais faut pas oublier de l'inclure à la compilation.

 
Oui en C. Mais là il veut juste l'algo

 
tu as raison, c'est plus performant. Mais bon, ma proposition c'était pour faire simple (les optimisations viennent après).

 
Tu ne comprends pas pourquoi il suffit de tester jusqu'à la racine carrée ? C'est trivial : suppose un diviseur p de n supérieur à sqrt(n), alors il existe un q tel que pq = n. Mais ce q est évidemment plus petit que sqrt(n) et a donc déjà été testé.

2 <= x <= sqr(y)
 
Personne pour le crible d'Eratosthène ? Ca n'a rien de compliqué.

 
De fait, c'est trivial.
 
Me sens con, pour le coup.

2 < x <= sqr(y)

euh non, finalement c'etait juste...

pour le fun http://fabrice.bellard.free.fr/mersenne.html

Estil _vraiment_ nécessaire d'écrire ce programme sur une seule ligne ?
 
J'veux la version BrainFuck, je comprends pas bien le C.

 
Bon, je m'y colle !
 
Le crible d'Érathosthène est un tableau des nombres entiers que l'on écrit bien rangé :
 

 
C'est plus pratique quand c'est bien rangé, mais, c'est pas obligé ; d'ailleurs on peut aussi faire des lignes de n'importe quelle longueur et ça simplifie beaucoup si on choisit une longueur multiple de petits nombres premiers, 2, 3, 5. La dimension du tableau est limitée uniquement par le courage du réalisateur... On peut bien aller jusqu'à un milliard si l'on veut...
 
Le but du jeu est de barrer les nombres au fur et à mesure que l'on découvre qu'ils ne sont pas premiers. On fait une exception pour 1, qui, selon les auteurs, peut être considéré comme premier ou pas premier. On considère pour la suite qu'il n'est pas premier. Donc on commence en cherchant le plus petit nombre qui n'a pas encore été barré (exception pour le 1 : on suppose qu'il est barré). C'est donc 2. Et on barre tous les multiples de ce nombre : 2*2=4, 2*3=6, etc... Si le tableau est bien rangé, on s'aperçoit vite que les multiples de deux, forment des séries géométriquement faciles à repérer. Ici, ce sont cinq colonnes, les colonnes du 2 (sauf le 2, bien sûr), du 2, du 6, du 8 et du 10. D'un coup on a barré tous les multiples de 2.
 
Ensuite on cherche à nouveau le plus petit nombre qui n'a pas encore été utilisé et qui n'est pas barré, donc le 3. On veut barrer 2*3 ; mais c'est déjà barré puisque 2*3 est multiple de 2 aussi. On barre donc à partir de 3*3 ; puis 3*4, 3*5, 3*6, etc...
Et là on s'aperçoit, dans le cas ci-dessus, que les nombres barrés sont alignés sur des diagonales : 12 et 21, 6-15-24-33-42-51, 9-18-27-36-45-54-63-72-81, 30-39-48-57-66-75-84-93-102-111, etc...
 
Ensuite on cherche à nouveau le plus petit nombre qui n'a pas encore été utilisé et qui n'est pas barré, donc le 5. On veut barrer 2*5 ; mais c'est déjà barré puisque 2*5 est multiple de 2 aussi. On veut barrer 3*5 ; mais c'est déjà barré puisque 3*5 est multiple de 3 aussi. On barre donc à partir de 5*5 et là aussi, les multiples de cinq sont bien alignés en deux colonnes (dont l'une est déjà barrée comme multiple de 2).
 
Et ainsi de suite ; ce n'est pas un hasard que le premier nombre à barrer lorsque l'on prend 3, soit 3*3, que le premier nombre à barrer lorsque l'on prend 5 soit 5*5. C'est systématique : puisque, lorsque l'on veut barrer les multiples de p, on est censé avoir barré tous les multiples des nombres premiers inférieurs à p, il est évident que le premier nombre à barrer sera p*p. Et cette remarque permet d'arrêter le processus, lorsque l'on tombe sur un premier p tel que p*p est plus grand que le dernier nombre du crible. Tous les nombres restants sont premiers, et aucun autre ne l'est.

bonne idée,
si la mémoire est limitée, y'a toujours ça :
 

 
tant qu'on y est, on peut afficher certains nombres premiers (comme Mersenne 42 et consorts) avec un programme beaucoup plus court que ça...