TP Python – Chercher et décomposer des nombres premiers

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S06

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Test de primalité

Écris est_premier(n). Teste les diviseurs de 2 à \(\sqrt{n}\) : la condition de la boucle est d * d <= n.

J'anticipe. Pour n = 91, quels diviseurs seront testés et à quel moment s'arrête la boucle ?

###

Lancer assert estpy-undpremier(0) is Falsebksl-nlassert estpy-undpremier(1) is Falsebksl-nlassert estpy-undpremier(2) is Truebksl-nlassert estpy-undpremier(4) is Falsebksl-nlassert estpy-undpremier(91) is Falsebksl-nlassert estpy-undpremier(97) is Truebksl-nlassert estpy-undpremier(997) is Truebksl-nlassert estpy-undpremier(1001) is Falsebksl-nlassert [k for k in range(50) if estpy-undpremier(k)] == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def estpy-undpremier(n):bksl-nl """True si l'entier n est premier."""bksl-nl if n < 2:bksl-nl return Falsebksl-nl d = 2bksl-nl # À compléter : tant que d py-str d <= n, si d divise n alors n n'est pas premier ; sinon d augmente de 1bksl-nl return Truebksl-nlbksl-nl

---

---

Exercice B – Le crible d'Ératosthène

Écris crible(N) qui renvoie la liste des nombres premiers inférieurs ou égaux à \(N\), à l'aide d'une liste de booléens.

###

Lancer assert crible(1) == []bksl-nlassert crible(2) == [2]bksl-nlassert crible(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]bksl-nlassert len(crible(100)) == 25bksl-nlassert crible(100)[-1] == 97bksl-nlassert len(crible(1000)) == 168bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def crible(N):bksl-nl """Liste des nombres premiers <= N (crible d'Ératosthène)."""bksl-nl estpy-undpremier = [True] py-str (N + 1)bksl-nl # À compléter : 0 et 1 ne sont pas premiers ;bksl-nl # pour p de 2 à racine de N, si p est encore marqué premier,bksl-nl # marquer False tous ses multiples à partir de p py-str p.bksl-nl return [k for k in range(N + 1) if estpy-undpremier[k]]bksl-nlbksl-nl

---

---

Exercice C – Décomposition en facteurs premiers

Écris decomposition(n) qui renvoie un dictionnaire {premier: exposant}, par exemple {2: 3, 3: 2, 5: 1} pour 360.

Je comprends. Pourquoi suffit-il de boucler tant que d * d <= n et de traiter le reste à part ?

###

Lancer assert decomposition(360) == {2: 3, 3: 2, 5: 1}bksl-nlassert decomposition(2) == {2: 1}bksl-nlassert decomposition(97) == {97: 1}bksl-nlassert decomposition(1001) == {7: 1, 11: 1, 13: 1}bksl-nlassert decomposition(1024) == {2: 10}bksl-nlassert decomposition(2024) == {2: 3, 11: 1, 23: 1}bksl-nlassert decomposition(3233) == {53: 1, 61: 1}bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def decomposition(n):bksl-nl """Dictionnaire {premier: exposant} de la décomposition de n >= 2."""bksl-nl resultat = {}bksl-nl d = 2bksl-nl while d py-str d <= n:bksl-nl while n % d == 0:bksl-nl resultat[d] = resultat.get(d, 0) + 1bksl-nl n = n // dbksl-nl d = d + 1bksl-nl # À compléter : s'il reste un facteur n > 1, c'est un nombre premierbksl-nl return resultatbksl-nlbksl-nl

---

---

Exercice D – Nombre de diviseurs

Écris nombre_de_diviseurs(n) à partir de la décomposition (produit des exposants augmentés de 1).

###

Lancer assert nombrepy-unddepy-unddiviseurs(1) == 1bksl-nlassert nombrepy-unddepy-unddiviseurs(13) == 2bksl-nlassert nombrepy-unddepy-unddiviseurs(36) == 9bksl-nlassert nombrepy-unddepy-unddiviseurs(360) == 24bksl-nlassert nombrepy-unddepy-unddiviseurs(1024) == 11bksl-nlassert nombrepy-unddepy-unddiviseurs(5040) == 60bksl-nlassert all(nombrepy-unddepy-unddiviseurs(k) == len([d for d in range(1, k + 1) if k % d == 0]) for k in range(1, 300))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def decomposition(n):bksl-nl resultat = {}bksl-nl d = 2bksl-nl while d py-str d <= n:bksl-nl while n % d == 0:bksl-nl resultat[d] = resultat.get(d, 0) + 1bksl-nl n = n // dbksl-nl d = d + 1bksl-nl if n > 1:bksl-nl resultat[n] = resultat.get(n, 0) + 1bksl-nl return resultatbksl-nlbksl-nldef nombrepy-unddepy-unddiviseurs(n):bksl-nl """Nombre de diviseurs positifs de n >= 1."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – Premiers palindromes

Un nombre est un palindrome si son écriture décimale se lit de la même façon dans les deux sens (131, 757…). Écris premiers_palindromes(N) qui renvoie la liste croissante des nombres premiers palindromes inférieurs ou égaux à \(N\).

###

Lancer assert premierspy-undpalindromes(10) == [2, 3, 5, 7]bksl-nlassert premierspy-undpalindromes(200) == [2, 3, 5, 7, 11, 101, 131, 151, 181, 191]bksl-nlassert premierspy-undpalindromes(1) == []bksl-nlassert len(premierspy-undpalindromes(1000)) == 20bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def estpy-undpremier(n):bksl-nl if n < 2:bksl-nl return Falsebksl-nl d = 2bksl-nl while d py-str d <= n:bksl-nl if n % d == 0:bksl-nl return Falsebksl-nl d = d + 1bksl-nl return Truebksl-nlbksl-nldef premierspy-undpalindromes(N):bksl-nl """Liste croissante des nombres premiers palindromes <= N."""bksl-nl ...bksl-nlbksl-nl

---

---