Aller au contenu

Découverte des tests de primalité⚓︎

Rappels

  • Un nombre premier est un entier \(n>1\) qui n'a que deux diviseurs,
  • les autres sont dits composés.
  • \(1\) n'est ni premier, ni composé.

Dans cette section \(n>1\), sera donc soit premier, soit composé.

n tours de boucle⚓︎

Petit diviseur⚓︎

\(1\) et \(n\) sont toujours des diviseurs de \(n\), ainsi dans \([2 ; n]\) il y en a au moins un.

Écrire une fonction petit_diviseur(n) dans une console Basthon qui renvoie le plus petit (hors \(1\)) diviseur de \(n\).

Vérifier

>>> petit_diviseur(2)
2
>>> petit_diviseur(3)
3
>>> petit_diviseur(4)
2
>>> petit_diviseur(5)
5
>>> petit_diviseur(9)
3

Grand diviseur⚓︎

\(1\) et \(n\) sont toujours des diviseurs de \(n\), ainsi dans \([1 ; n-1]\) il y en a au moins un.

Écrire une fonction grand_diviseur(n) dans une console Basthon qui renvoie le plus grand (hors \(n\)) diviseur de \(n\).

Vérifier

>>> grand_diviseur(2)
1
>>> grand_diviseur(3)
1
>>> grand_diviseur(4)
2
>>> grand_diviseur(5)
1
>>> grand_diviseur(9)
3

Test de primalité - version 1⚓︎

Écrire une fonction est_premier(n) qui renvoie un booléen

  • True si \(n\) est premier,
  • False sinon.

Vérifier

>>> est_premier(7)
True
>>> est_premier(25)
False
>>> est_premier(32)
False
>>> est_premier(101)
True
Solution
  • On commence une boucle avec \(d = 2\), les diviseurs candidats.
  • Tant que \(d < n\),
    • on teste si \(d\) est un diviseur
    • et on incrémente \(d\) de \(1\), pour passer au suivant.
  • On rappelle qu'on travaille ici dans \(\mathbb N^*\),
    • on ne traite pas ici le cas \(d=0\).
def est_divible(n, d):
    return n % d == 0

def est_premier(n):
    """Renvoie `True` ou `False` selon que
    `n` est un nombre premier ou non.
    """
    if n < 2:
        return False
    d = 2
    while d < n:
        if est_divisible(n, d):
            return False
        d = d + 1
    return True

Tests en pratique⚓︎

  1. Utiliser ce test de primalité sur les nombres de Mersenne. Jusqu'où allez-vous ?
  2. Utiliser ce test de primalité sur les nombres de Fermat. Jusqu'où allez-vous ?
  3. Donner les images petit_diviseur(F(n)) et petit_diviseur(M(n)) que vous pouvez trouver.

Factorielle ±1⚓︎

Pour \(n>2\).

  1. Justifier pourquoi \(n! ±2\) est composé.
  2. Justifier pourquoi \(n! ±3\) est composé.
  3. Généraliser !
  4. Justifier pourquoi Factorielle(n)±1 est un bon candidat pour être premier.

Utiliser votre test de primalité pour trouver des nombres premiers de la forme \(n! ±1\).

√(n) tours de boucle⚓︎

  1. Justifier que si \(n\) ne possède aucun diviseur \(1<d\leqslant \sqrt{n}\), alors \(n\) est premier.
  2. Modifier alors votre test de primalité pour le rendre plus efficace.
  3. Reprendre tous les tests en pratique ! Alors ?
Solution

Il suffit de modifier une ligne

def est_divible(n, d):
    return n % d == 0

def est_premier(n):
    """Renvoie `True` ou `False` selon que
    `n` est un nombre premier ou non.
    """
    if n < 2:
        return False
    d = 2
    while d*d <= n:
        if est_divisible(n, d):
            return False
        d = d + 1
    return True