L’exercice prétexte : la fonction is_prime

Cette fonction prend un entier n positif ou nul en entrée et retourne True si et seulement si n est un nombre premier.

Définition d’un nombre premier

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.

En partant de cette définition, on serait tenté, pour coder en python une fonction is_prime testant la primalité d’un entier d’énumérer tous les diviseurs du nombre et constater qu’il y en a exactement deux. Ce n’est en général pas ce qu’on fait.

On peut aussi remarquer que n est premier si et seulement si n est supérieur ou égal à 2 et qu’aucun entier entre 2 et n-1 ne divise n. Ci-dessous une première définition sur ce principe :

Quelques appels à is_prime

>>> some_int = [11, 8, 2, 0, -1, 151]
>>>for n in some_int:
      ...print(f'{n:3d} est-il premier ? {is_prime(n)}')
 11 est-il premier ? True
  8 est-il premier ? False
  2 est-il premier ? True
  0 est-il premier ? False
 -1 est-il premier ? False
151 est-il premier ? True

Et l’efficacité ?

Dans un interprète ipython, on peut utiliser %timeit pour mesurer le temps d’exécution d’une instruction.

>>> pair = 79991172
>>> %timeit is_prime(pair)
5.41 s ± 178 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

On constate un très long temps de réponse alors que le nombre est pair. Bien sûr cela est dû à la boucle for : alors même que l’on détecte immédiatement que 2 divise pair, la boucle poursuit jusqu’à la fin. Il convient donc de s’arrêter dès la détection d’un diviseur. Voici une autre version tenant compte de cette remarque :

>>> %timeit is_prime(pair)
230 ns ± 1.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Voilà qui est mieux. Testons cette fois avec un nombre premier.

>>> grand = 79991173
>>> %timeit is_prime(grand)
8.74 s ± 9.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Comme on le constate, le temps de calcul est important pour détecter la primalité d’un entier de l’ordre de la dizaine de millions ; ça ne semble pas très efficace. On peut améliorer les choses en constatant que la recherche d’un diviseur potentiel peut s’arrêter à int(sqrt(n))+1 :

>>> %timeit is_prime(grand)
3.11 ms ± 67.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Nous voilà avec un temps de réponse acceptable.

Mais quid de la clarté ?

Clairement ce code n’est pas très proche de la définition en langage courant, dont on rappelle qu’elle est :
n est premier ssi n > 1 et pour tout les entiers d entre 2 et racine carrée de n, d ne divise pas n. La clarté du code précédent pourrait amélioré en revenant à une boucle for et l’utilisation de plusieurs instructions return

>>> %timeit is_prime(grand)
596 µs ± 4.82 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

On constate, en plus d’avoir un code plus court, et probablement plus lisible, un gain en temps de réponse.Mais cela reste perfectible : l’utilisation de plusieurs return peut ne pas plaire. Et même si on opte pour cette version :

La fonction all

all est une fonction prédéfinie python qui prend un iterable comme paramètre et retourne True si chaque élément de l’iterable est évalué à True ou si l’itérable est vide. Ci-dessous quelques exemples :

>>> all([True, True])
True
>>> all('hello')
True
>>> all('')
True
>>> all((3 > 2, is_prime(5)))
True

>>> all([is_prime(n) for n in range(10)])
False

Dans les exemples ci-dessus nous avons des itérables très classiques : listes, chaînes de caractères, tuples. Dans le dernier exemple nous utilisons une liste en compréhension. Cette idée peux être améliorée : un itérable peut être un itérateur, ici par exemple obtenu grâce à une expression génératrice.

Associons une expression génératrice

>>> all(is_prime(n) for n in [2, 3, 5, 7, 11])
True

Une expression génératrice est une expression de la forme :

(f(x) for x in iterateur)

Cette expression produit un itérateur. L’avantage principal d’un itérateur par rapport à un autre itérable comme les séquences, c’est qu’aucune structure n’est créée et donc un gain en mémoire appréciable. Ci-dessous quelques exemples de l’utilisation des expressions génératices :

>>> sum(x ** 2 for x in range(10))
285

>>> phrase = """Tu te jugeras donc toi-même, lui répondit le roi. C’ est le plus difficile. Il est bien plus difficile de se juger soi-même que de juger autrui"""
>>> s = set(mot.lower() for mot in phrase.split())
>>> print(s)
{'donc', 'soi-même', 'le', 'toi-même,', 'juger', 'il', 'bien', 'difficile.', 'lui', 'roi.', 'plus', 'se', 'autrui', 'de', 'te', 'jugeras', 'tu', 'est', 'que', 'difficile', 'répondit', 'c’'}

>>> phrase = phrase.lower()
>>> d = dict((c, phrase.count(c)) for c in phrase if 'a' <= c <= 'z')
>>> print(d)
{'t': 7, 'u': 10, 'e': 17, 'j': 3, 'g': 3, 'r': 6, 'a': 2, 's': 7, 'd': 6, 'o': 5, 'n': 3, 'c': 4, 'i': 14, 'm': 4, 'l': 8, 'p': 3, 'f': 4, 'b': 1, 'q': 1}

Nouvelle définition de is_prime

Notons que nous retrouvons la clarté de la définition en langage naturel. Il nous reste à vérifier que le temps de réponse est au moins aussi bon qu’avant :

>>> %timeit is_prime(grand)
915 µs ± 3.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Dernier point à vérifier : est-ce que la découverte d’un diviseur stoppe l’itération ?

Première vérification

>>> %timeit is_prime(pair)
1.16 µs ± 1.82 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Deuxième vérification

Elle s’appuie sur la propriété suivante : un itérateur ne peut être utilisé qu’une fois.

>>> it = (x {{ 2 for x in range(5))
>>>
>>> # Première utilisation
>>> for n in it:
       ... print(n)
0
1
4
9
16
>>>

>>> # deuxième utilisation
>>> for n in it:
       ... print(n)
>>>

Comme on le constate, la deuxième itération ne produit rien : l’itérateur ayant servi une fois, il est vide la seconde fois.

>>> it2 = (d for d in range(2, int(sqrt(pair))+1))
>>> all(pair % d for d in it2)
False

>>>for d in it2:
      ... if d < 6:
      ... ... print(d)
      ... else:
      ... ... break
3
4
5

it2 est donc un itérateur des entiers de 2 à la racine carrée de notre grand nombre pair. La première fois nous l’utilisons dans la fonction all puis une seconde fois pour afficher quelques unes des valeurs. On constate que it2 n’a été utilisée par la fonction all que pour la première valeur (2) et donc la deuxième utilisation commence à 3.

Conclusion

Mal connue, la fonction all associée aux expressions génératrices offre à la fois une concision et une simplicité d’écriture proche du langage naturel sans perdre en performance. Elle mérite donc de figurer dans les concepts à enseigner même aux débutants. A noter que la fonction any propose les mêmes avantages.