Tamis d'eratosthènes avec C ++

Un nombre premier est un nombre naturel (entier) qui est supérieur ou égal à deux, qui ne peut être divisé par lui-même et 1. Les premiers nombres premiers sont: 2, 3, 5, 7, etc.

Pour le numéro 5, le nombre de nombres premiers qui sont jusqu'à et / ou incluant 5 sont:

2, 3, 5

Pour le numéro 8, le nombre de nombres premiers qui sont jusqu'à et / ou incluant 8 sont:

2, 3, 5, 7

Pour le numéro 19, le nombre de nombres premiers qui représentent et / incluant 19 sont:

2, 3, 5, 7, 11, 13, 17, 19

Pour le nombre 25, le nombre de nombres premiers qui sont jusqu'à et / ou incluant 25 sont:

2, 3, 5, 7, 11, 13, 17, 19, 23

Pour le nombre 36, le nombre de nombres premiers qui sont jusqu'à et / ou incluant 36 sont:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Pour le nombre 37, le nombre de nombres premiers qui sont jusqu'à et / ou incluant 37 sont:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Ces listes ne sont que des exemples. Il existe de nombreux autres exemples de listes de nombres premiers ci-dessous et / ou y compris un numéro donné. Commencez à comprendre le tamis des eratosthènes en notant que les nombres premiers inférieurs à un nombre donné plus petit sont les mêmes que la première partie des nombres premiers en dessous d'un nombre plus grand donné.

Le tamis des eratosthènes est une technique pour trouver tous les nombres premiers qui sont inférieurs ou égaux à un nombre donné tels que 36 ou 37 ci-dessus. Ce nombre tel que 36 ou 37 reçoit généralement le nom de variable «n» dans la programmation. Le tamis des eratosthènes est considéré comme un algorithme efficace pour obtenir la liste des nombres premiers.

Démonstration pour tamis d'eratosthène

La question est: trouvez les nombres premiers inférieurs ou égaux à 5, par exemple, de manière efficace. La manière efficace ici signifie utiliser le moins d'opérations que possible. Les nombres premiers commencent à partir de 2. Tous les nombres, y compris les multiples de petits nombres premiers de 2 à 5, sont:

2, 3, 4, 5

Dans cette gamme, un nombre qui n'est pas un nombre premier est un multiple d'un nombre premier précédent. Un multiple peut être obtenu par addition du même numéro de premier ordre, encore et encore. Par exemple, 2 + 2 est 4, plus 2 à nouveau est 6. Et cela se passe au-delà de la gamme. Quatre, qui est un multiple de 2, ne devrait pas figurer sur la liste car ce n'est pas un nombre premier. L'équation 3 + 3 est 6, ce qui est déjà au-delà de la plage. Et 6 ou n'importe quel nombre au-delà de la plage ne devrait pas figurer sur la liste. Donc, le résultat est le suivant:

2, 3, 5

Le nombre en question ici est 5. La racine carrée de 5 est 2.24. La valeur entière pour la racine carrée de 5 est 2. Les multiples de nombres premiers en dessous et jusqu'à 2, qui est la valeur entière pour la racine carrée de 5, sont supprimées de la liste de tous les nombres.

Considérez maintenant, le numéro 8. Tous les nombres, y compris les multiples de petits nombres premiers de 2 à 8, sont:

2, 3, 4, 5, 6, 7, 8

L'équation 2 + 2 est 4. Quatre sort. L'équation 4 + 2 est 6. Six sort. L'équation 6 + 2 est 8. Huit est sorti. Le prochain numéro de premier ordre à considérer est 3. L'équation 3 + 3 est 6. Six est déjà exclu par l'ajout continu de 2. L'équation 6 + 3 est 9; qui est hors de portée. Les nombres premiers entre 2 et 8, inclusifs, sont:

2, 3, 5, 7

Le nombre en question ici est 8. La racine carrée de 8 est 2.83. La valeur entière pour la racine carrée de 8 est 2. Les multiples des nombres premiers en dessous et jusqu'à 2 qui est la valeur entière de la racine carrée de 8 sont supprimés pour obtenir la liste requise des nombres premiers.

Un problème similaire consiste à énumérer les nombres premiers de 2 à 19, inclusivement. Tous les nombres de 2 à 19, inclusifs sont:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

L'équation 2 + 2 est 4; 4 est sorti. L'équation 4 + 2 est 6; 6 est sorti. L'équation 6 + 2 est 8; 8 est sorti. L'équation 8 + 2 est 10; 10 est sorti. L'équation 10 + 2 est 12; 12 est sorti. L'équation 12 + 2 est 14; 14 est sorti. L'équation 14 + 2 est 16; 16 est sorti. L'équation 16 + 2 est 18; 18 est sorti. L'équation 18 + 2 est de 20, ce qui est au-dessus de la plage; 20 est sorti.

Le numéro principal suivant à considérer, montant vers la racine carrée de 19, est 3. L'équation 3 + 3 est 6; 6 est déjà exclu comme un multiple de 2. L'équation 6 + 3 est 9; 9 sort. L'équation 9 + 3 est 12; 12 est déjà exclu comme un multiple de 2. L'équation 12 + 3 est de 15; 15 est sorti. L'équation 15 + 3 est 18; 18 est déjà exclu comme un multiple de 2. L'équation 18 + 3 est 21, ce qui est au-dessus de la plage. Le résultat est:

2, 3, 5, 7, 11, 13, 17, 19

Le nombre en question ici est 19. La racine carrée de 19 est 4.36. La valeur entière pour la racine carrée de 19 est 4. Les multiples de nombres premiers en dessous et jusqu'à 4 qui est la valeur entière pour la racine carrée de 19 sont supprimées.

Les nombres premiers en dessous et jusqu'à 4 sont: 2 et 3. En raison de 3, il était inutile de supprimer les nombres 6, 12 et 18 qui sont des multiples de 3, qui sont déjà supprimés sous forme de multiples de 2. Seuls les multiples de 3 qui ne sont pas des multiples de 2 sont supprimés à cause de 3. En pratique, après avoir retiré les multiples de 2, seuls les multiples de 3 x 3 = 9 doivent être retirés sans répéter le retrait de 6. En raison de 3, les chiffres à supprimer sont de 9, 12, 15 et 18; avec 12 et 18 supprimés deux fois en théorie. Le numéro 6 doit être supprimé une fois et non deux fois.

Soit N 25, un nouveau numéro en question. Tous les nombres de 2 à 25 sont:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

L'équation 2 + 2 est 4; 4 sort. L'équation 4 + 2 est 6; 6 est sorti. L'équation 6 + 2 est 8; 8 est sorti. L'équation 8 + 2 est 10; 10 est sorti. L'équation 10 + 2 est 12; 12 est sorti. L'équation 12 + 2 est 14; 14 est sorti. L'équation 14 + 2 est 16; 16 est sorti. L'équation 16 + 2 est 18; 18 est sorti. L'équation 18 + 2 est de 20; 20 est sorti. L'équation 20 + 2 est 22; 22 est sorti. L'équation 22 + 2 est 24; 24 est sorti. L'équation 24 + 2 est 26, ce qui est au-dessus de la plage.

Le numéro principal suivant à considérer, montant vers la racine carrée de 25, est 3. L'équation 3 + 3 est 6; 6 est déjà exclu comme un multiple de 2. L'équation 6 + 3 est 9; 9 sort. L'équation 9 + 3 est 12. Douze est déjà exclu comme un multiple de 2. L'équation 12 + 3 est de 15; 15 est sorti. L'équation 15 + 3 est 18; 18 est déjà exclu comme un multiple de 2. L'équation 18 + 3 est de 21; 21 sort. L'équation 21 + 3 est 24; 24 est déjà exclu comme un multiple de 2. L'équation 24 + 3 est 27, qui est au-dessus de la plage.

Le numéro principal suivant à considérer, en montant vers la racine carrée de 25 qui est de 5, est 5. L'équation 5 + 5 est de 10; 10 est déjà exclu comme un multiple de 2. L'équation 10 + 5 est de 15; 15 est déjà exclu comme un multiple de 3. L'équation 15 + 5 est de 20; 20 est déjà exclu comme un multiple de 2. L'équation 20 + 5 est de 25; 25 sort. Le résultat est:

2, 3, 5, 7, 11, 13, 17, 19, 23

Le nombre en question ici est 25. La racine carrée de 25 est 5. La valeur entière pour la racine carrée de 25 est 5. Les multiples de nombres premiers en dessous et jusqu'à 5, qui est la valeur entière pour la racine carrée de 25, sont supprimées.

Les nombres premiers en dessous et jusqu'à 5 sont 2, 3 et 5. En raison de 2, les nombres qui sont censés être supprimés de la liste de tous les nombres par multiples sont: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 et 24. En raison de 3, les nombres qui sont censés être supprimés de la liste par les multiples sont: 6, 9, 12, 15, 18, 21 et 24. En raison de 5, les nombres qui sont censés être supprimés par les multiples sont: 10, 15, 20 et 25.

Par tous les multiples, les éliminations sont les suivantes:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

Par multiples, 6 est supprimé deux fois (en théorie), 10 est supprimé deux fois (en théorie), 12 est supprimé deux fois (en théorie), 15 est supprimé deux fois (en théorie), 20 est supprimé deux fois (en théorie), et 24 est supprimé deux fois (en théorie).

Cependant, si en raison de 3, le retrait commence à 3 x 3 = 9, alors 6 n'est retiré qu'une seule fois. Si en raison de 5, le retrait commence à 5 x 5 = 25, alors le retrait de 10, 15 et 20 est effectué une fois chacun. Cependant, la suppression de 12, 18 et 24 est encore effectuée deux fois par nombre. Pourtant, il y aurait un avantage, car quatre opérations répétées de retrait sont omises (pour 6, 10, 15 et 20). Cela améliore l'efficacité (complexité temporelle). Avec cela, les déménagements seront:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

Les nombres 6, 10, 15 et 20 ont chacun été supprimés une fois, au lieu de deux fois. Les chiffres, 12, 18 et 24 ont chacun été retirés deux fois. À partir de maintenant, rien ne peut être fait pour enlever 12, 18 et 24 une seule fois.

Les situations pour les nombres 36 et 37, ou tout autre nombre supérieur à 1, sont expliquées de la même manière.

Éviter la redondance

En supprimant simplement les multiples de nombres premiers de 2 à la valeur entière de √n, l'ensemble requis de nombres premiers est obtenu. L'efficacité peut être améliorée en supprimant les multiples de nombres premiers, à partir du carré du nombre supérieur (i²) jusqu'à la valeur entière de √n comme indiqué précédemment. Cela omet quelques opérations de suppression des nombres. Donc, réduisant le nombre total d'opérations. Le tamis des eratosthènes se fait par cette deuxième approche.

Algorithme de tamis d'eratosthène

L'algorithme commence par fabriquer un vecteur indexé zéro de longueur qui est n + 1. Chaque élément de ce vecteur est initialisé à Boolean, vrai, à l'exception des premier et deuxième éléments pour l'index 0 et l'index 1 qui sont initialisés en false. Pour ce vecteur, l'index 2 correspond au nombre (prime) 2; L'indice 3 correspond au nombre (prime) 3; L'index 4 correspond au nombre 4; et ainsi de suite. Puisque le vecteur est nul un indice basé sur un.

Un numéro d'index pour cette liste de vecteurs qui doit être supprimée n'est pas supprimé en soi: la valeur du numéro d'index est rendue fausse pour indiquer la suppression. C'est-à-dire que l'élément reçoit la fausse valeur. Ainsi, si un nombre (index) doit être supprimé de la liste (vecteur) plus d'une fois, la valeur de l'index est rendue fausse plus d'une fois.

À la fin, les index pour les éléments du vecteur dont les valeurs sont restés vraies sont lues comme les nombres premiers.

Avant cela, les multiples des index principaux commençant par le carré de l'index principal (i²) jusqu'à la valeur entière de √n sont marqués comme faux.

Codage C ++

Le programme en C ++ devrait commencer par ce qui suit:

#inclure
#inclure
Utilisation de Namespace Std;

La fonction tamis des eratosthènes est la suivante:

vecteur tamis (int n)
vecteur tamis (n + 1, vrai);
tamis [0] = false;
tamis [1] = false;
int i = 2;
pendant que (je * je <= n)
if (sieve [i] == true) // si je suis un nombre premier
int j = i * i;
tandis que (J <= n) //marking multiples with false
tamis [j] = false;
j = j + i; // incrément par plusieurs


i = i + 1; // Incrément normal de la boucle externe, par 1

retour tamiser;

Lisez les commentaires du code. Le nom de la fonction est Sieve (). Le vecteur retourné, une fois que tous les multiples sont marqués comme faux, est également appelé tamis. Une fonction principale C ++ appropriée pour ce code est:

int main (int argc, char ** argv)

vecteur vtr = tamis (37);
pour (int i = 0; iif (vtr [i] == true)
couter << i << ";
couter << endl;
retour 0;

Avec ce code, la sortie est la suivante:

2 3 5 7 11 13 17 19 23 29 31 37

La complexité temporelle de cette fonction est O (n log log n).

Conclusion

L'algorithme commence par fabriquer un vecteur indexé à base de zéro de la longueur n + 1. Chaque élément de ce vecteur est initialisé à Boolean, vrai, à l'exception des premier et deuxième éléments pour l'index 0 et l'index 1 qui sont initialisés en false. Pour ce vecteur, chaque index est un certain nombre d'intérêt. Puisque le vecteur est indexé à base de zéro, la longueur doit être n + 1 pour que le dernier index soit n.

La valeur du nombre qui est l'indice est rendue fausse pour indiquer la suppression. C'est-à-dire que l'élément reçoit la fausse valeur.

À la fin, les index pour les éléments du vecteur dont les valeurs sont restés vraies sont lues comme les nombres premiers.

Avant cela, les multiples des index principaux commençant par le carré de l'index principal jusqu'à la valeur entière de √n sont marqués comme faux.