1. Le crible d’Ératosthène.
Une méthode pour calculer tous les nombres premiers inférieurs à un certain entier positif fixé \(N\) consiste à lister tous les entiers \(n\) tels que \(1 \lt n \lt N\text{.}\) Commencez par éliminer tous les multiples de \(2\text{.}\) Ensuite, éliminez tous les multiples de \(3\text{.}\) Éliminez maintenant tous les multiples de \(5\text{.}\) Remarquez que \(4\) a déjà été barré. Continuez ainsi, en notant qu’il n’est pas nécessaire d’aller jusqu’à \(N\) ; il suffit de s’arrêter à \(\sqrt{N}\text{.}\) En utilisant cette méthode, calculez tous les nombres premiers inférieurs à \(N = 250\text{.}\) On peut aussi utiliser cette méthode pour trouver tous les entiers premiers avec un entier \(N\text{.}\) Il suffit d’éliminer les facteurs premiers de \(N\) et tous leurs multiples. En utilisant cette méthode, trouvez tous les entiers premiers avec \(N= 120\text{.}\) En utilisant le crible d’Ératosthène, écrivez un programme qui calculera tous les nombres premiers inférieurs à un entier \(N\text{.}\)
