Exercices Python d’arithmétique

Exercice (facteurs premiers, diviseurs)

  1. Écrire une fonction ppdiv(n) qui renvoie le plus petit diviseur premier d’un entier {n\ge 2}.
    En déduire une fonction très simple estpremier qui renvoie True ou False selon que n est premier ou non.
  2. Écrire une fonction facteurs(n) renvoyant la liste des facteurs premiers de {n\ge 2}. Par exemple facteurs(1234000) doit renvoyer la liste [2,2,2,2,5,5,5,617].
  3. Écrire une fonction diviseurs(n) renvoyant la liste ordonnée des diviseurs de {n\ge 2} dans {\mathbb{N}^*}. Par exemple diviseurs(30) doit renvoyer la liste [1,2,3,5,6,10,15,30].


Exercice (crible d’Eratosthène)
Le crible d’Eratosthène est une méthode artisanale pour former la liste de tous les nombres premiers inférieurs ou égaux à un entier n donné.
On part de la liste de tous les entiers de 2 à n. On en efface les multiples de 2 (sauf 2 lui-même) puis tous les multiples de 3 (sauf 3 lui-même), etc.
La progression se fait toujours vers le plus petit entier p non encore effacé (il est donc premier) et elle consiste à effacer tous les multiples de p (sauf p lui-même, et le premier entier à effacer est {p^2}).
On s’arrête quand {p^2\ge n} (car il n’y a alors plus rien à effacer), et les entiers restants sont les entiers premiers de l’intervalle {[2, n]}.
En s’inspirant de cette méthode, on cherche à écrire une fonction crible prenant en argument un entier {n\ge 2} et renvoyant la liste de tous les entiers premiers de l’intervalle {[2, n]}.

On voit pour cela deux méthodes possibles (assez voisines) :

  1. On forme une liste L de L+1 booléens (True ou False). À la fin, L[p] contiendra True si p est premier (et False sinon). Donc barrer k, c’est écrire L[k]=False. Au début, L[0] et L[1] valent False, et les suivants valent True.
    On entre ensuite dans une boucle de {p=2} à {p=\sqrt{n}}. Si p n’est pas barré, on barre ses multiples (les kp, avec {k\ge p}). À la fin de cette boucle, il suffit de former la liste des entiers p tels que L[p] contient True.
  2. Variante (plus avancée) : on reprend l’idée précédente, mais on utilise un tableau Numpy de booléens.
    Le module Numpy permet en effet de modifier simultanément toute une coupe d’éléments d’un tableau (ce qui rend beaucoup plus simple la phase « barrer les multiples »).


Exercice (entiers premiers jumeaux)
On dit que deux entiers premiers sont jumeaux s’ils s’écrivent {p} {p+2}. Une conjecture célèbre dit que leur nombre est infini. Écrire une fonction jumeaux(n) renvoyant la liste des couples {(p,p+2)} d’entiers premiers jumeaux où {p\le n}.
On utilisera la fonction crible de l’exercice 2.


Exercice (conjecture de Goldbach)
La conjecture de Goldbach affirme que tout entier pair {n\ge 4} peut s’écrire comme la somme de deux entiers premiers.

Écrire une fonction goldbach prenant en argument un entier {n\ge 4} (supposé pair) et renvoyant la liste des couples {(p,p')} d’entiers premiers tels que {n=p+p'}, avec {p\le p'}.
On utilisera la fonction crible de l’exercice 2.