devoir4-sujet

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 :

On initialise une liste 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.
On affecte à T[0] et T[1] la valeur False (ce ne sont pas des nombres premiers).
Ensuite, on parcourt la liste de l'indice $i = 2$ à $N-1$. Pour chaque valeur de $i$, si 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.
Lorsqu'on a terminé avec $i = N-1$, on s'arrête et on retourne la liste des indices $i$ tels que 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.

Devoir de la semaine 4 : nombres premiers et crible d'Eratosthène¶