à rendre sur Moodle avant le 21/02/2022, 15h00
Le crible d'Ératosthène permet d'obtenir la liste des nombres premiers entre $0$ et $N-1$, pour un certain entier $N$. L'idée du crible est la suivante :
T
de longueur N
, qui ne contient que des valeurs booléennes égales à True
. La liste T
a pour vocation de savoir quels sont les nombres premiers. Le but est qu'à la fin de l'algorithme, T[i]
vaut True
si i
est un nombre premier.T[0]
et T[1]
la valeur False
(ce ne sont pas des nombres premiers).T[i]
est vrai, alors on modifie T[j]
en False
pour tous les $j > i$ tels que $i$ divise $j$. L'idée est que comme $i$ divise strictement $j$, l'entier $j$ ne peut pas être premier.T[i]
vaut True
.Pour plus de détails sur le fonctionnement du crible, voir par exemple la page wikipedia :
https://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Question 1 : Écrire une fonction initialiser_tableau(N)
qui retourne une liste de longueur $N$ ne comportant que la valeur True
.
Question 2 : Écrire une fonction eliminer_diviseurs(T, p, N)
qui prend en entrée une liste de booléens T
, un entier $p \ge 2$ et la taille $N$ de la liste, et qui modifie la liste T
en affectant False
à T[j]
pour tous les indices $j$ divisibles par $p$ et strictement supérieurs à $p$. Pour faire cela, on pourra parcourir les indices de la liste par pas de $p$.
Par exemple, si en entrée de la fonction la liste est égale
T = [True, True, True, True, False, True, False, True, False, True, False, True, False, True, False, True]
avec une taille N = 16
et l'entier p = 3
, alors en sortie la liste T
devient :
T = [True, True, True, True, False, True, False, True, False, False, False, True, False, True, False, False]
(les valeurs d'indice $6$, $9$, $12$ et $15$ sont égales à False
).
Question 3 : À l'aide des questions précédentes, implanter le crible d'Eratosthène présenté en début d'exercice, sous la forme d'une fonction eratosthene(N)
qui retourne la liste des nombres premiers compris entre $2$ et $N$.
On vérifiera que pour eratosthene(100)
, on obtient la liste :
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
On dit que $p$ est un nombre premier de Sophie Germain si $p$ et $2p+1$ sont des nombres premiers.
Question 4 : Écrire une fonction premiers_sophie_germain(N)
qui retourne la liste des nombres premiers de Sophie Germain inférieurs ou égaux à N
.
Remarque : vous pouvez implanter cette question en admettant avoir réussi la question précedente, c'est-à-dire en supposant que eratosthene
retourne la bonne liste (même si ce n'est pas le cas).
On dit que $p$ et $q$ sont deux nombres premiers jumeaux si $p$ et $q$ sont premiers et si $|p - q| = 2$.
Question 5 : Écrire une fonction premiers_jumeaux(N)
qui retourne la liste des nombres premiers jumeaux inférieurs ou égaux à N
.
Remarque : vous pouvez implanter cette question en admettant avoir réussi la question précedente, c'est-à-dire en supposant que eratosthene
retourne la bonne liste (même si ce n'est pas le cas).