Heelp pls
Fermé
ibtissam_7886
Messages postés
1
Date d'inscription
Statut
Membre
Dernière intervention
-
Utilisateur anonyme -
Utilisateur anonyme -
L’inconvénient de l’algorithme naïf est qu’il effectue de nombreuses divisions inutiles.
Par exemple, il peut tester la divisibilité par 6 d’un entier qui n’est divisible ni par 3, ni par 2.
Ératosthène était un scientifique de l’antiquité, qui a proposé un algorithme appelé Crible
d’Ératosthène, qui permet d’éviter ces calculs inutiles.
L’algorithme du Crible d’Ératosthène pour déterminer les nombres premiers compris entre 2 et N
est le suivant :
On considère un tableau contenant tous les entiers de 2 à N .
On supprime tous les multiples de 2 (sauf 2).
Parmi les nombres restants, on supprime tous les multiples de 3 (sauf 3 ).
On répète ce traitement jusqu’à ce qu’il n’y ait plus de nombre à traiter.
Les nombres restants à la fin du traitement sont les nombres premiers recherchés.
1. Appliquez manuellement cet algorithme pour trouver les nombres premiers compris entre 1
et 30
Par exemple, il peut tester la divisibilité par 6 d’un entier qui n’est divisible ni par 3, ni par 2.
Ératosthène était un scientifique de l’antiquité, qui a proposé un algorithme appelé Crible
d’Ératosthène, qui permet d’éviter ces calculs inutiles.
L’algorithme du Crible d’Ératosthène pour déterminer les nombres premiers compris entre 2 et N
est le suivant :
On considère un tableau contenant tous les entiers de 2 à N .
On supprime tous les multiples de 2 (sauf 2).
Parmi les nombres restants, on supprime tous les multiples de 3 (sauf 3 ).
On répète ce traitement jusqu’à ce qu’il n’y ait plus de nombre à traiter.
Les nombres restants à la fin du traitement sont les nombres premiers recherchés.
1. Appliquez manuellement cet algorithme pour trouver les nombres premiers compris entre 1
et 30