Algorithmes numériques

Diviseurs et nombres premiers

Divisions successives par essai

Un entier $n \geq 2$ est premier si ses seuls diviseurs positifs sont 1 et $n$ ; s’il en a un autre, il est composé ; 0 et 1 ne sont ni l’un ni l’autre. La définition suggère aussitôt un algorithme : essayer chaque candidat $d$ entre 2 et $n - 1$ et déclarer le nombre composé dès que l’un d’eux le divise. C’est la boucle du plus petit diviseur de la leçon Boucles, et elle est correcte. Or, pour un nombre premier de dix chiffres, elle effectue presque dix milliards de divisions, et presque toutes sont inutiles, pour la raison suivante.

Il s’ensuit que le nombre de divisions passe d’environ $n$ à environ $\sqrt{n}$ : pour $n$ proche de deux milliards, de deux milliards à quarante-six mille. Le programme utilise le schéma du drapeau de la leçon Concevoir des boucles correctes : isPrime commence vrai et la boucle l’éteint si elle trouve un diviseur.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} est premier", n);    } else {        std::println("{} n’est pas premier", n);    }}

2147483647

2147483647 est premier

Trois décisions méritent un commentaire. Le drapeau est initialisé avec n >= 2, de sorte que 0, 1 et les nombres négatifs sont déclarés non premiers sans entrer dans la boucle : oublier ce cas est l’erreur typique, car avec $n = 1$ la boucle ne fait aucune itération et le programme déclarerait 1 premier. La condition du for a deux parties : le drapeau, qui arrête la boucle au premier diviseur, et la borne. Et la borne s’écrit d <= n / d, ce qui, pour des entiers strictement positifs, équivaut à $d^2 \leq n$ (la division entière tronque, mais $d$ ne dépasse pas le quotient tronqué exactement quand il ne dépasse pas $n/d$, car $d$ est entier). Le nombre de l’entrée, $2^{31} - 1$, est le plus grand int et il est premier ; le programme le décide avec $46\,339$ restes, ceux des candidats de 2 à $46\,340$.

L’invariant de la boucle est : aucun entier de 2 à $d - 1$ ne divise $n$, tant que le drapeau reste vrai. Il est vrai à l’entrée, quand l’intervalle de 2 à 1 est vide ; il se conserve, car si $d$ ne divise pas $n$, l’intervalle s’agrandit d’un nombre qui ne le divise pas ; et à la sortie avec le drapeau vrai, l’invariant et la condition fausse, $d^2 > n$, disent ensemble qu’aucun candidat jusqu’à $\sqrt{n}$ ne divise $n$, ce qu’exige la proposition. Le variant est le nombre de candidats qui restent à essayer, c’est-à-dire d’entiers entre $d$ et $\sqrt{n}$ : il décroît d’une unité par itération et ne descend pas au-dessous de zéro.

La condition qui déborde

La manière naturelle d’écrire la borne est d * d <= n, et c’est une erreur. Avec l’entrée précédente, la boucle atteint $d = 46\,341$, et alors le produit $46\,341^2 = 2\,147\,488\,281$ dépasse le maximum de int.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Premier ? {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Le détecteur de comportement indéfini arrête le programme au produit. Sans lui, le dépassement de capacité signé est un comportement indéfini, et la norme ne dit pas ce qui se passe. Ce que l’on observe avec GCC sous Linux, avec et sans optimisation, est instructif : le produit fait le tour et devient négatif ou plus petit que $n$, et comme aucun int ne dépasse le maximum, la condition d * d <= n ne cesse plus d’être vraie ; la boucle continue d’essayer des candidats pendant environ deux milliards d’itérations, jusqu’à atteindre $d = n$, qui divise $n$, et le programme déclare composé un nombre premier. Une erreur de dépassement ne se manifeste pas comme un dépassement, mais comme une réponse fausse. La forme d <= n / d ne peut pas déborder, car elle divise au lieu de multiplier ; la leçon Bits et bibliothèque mathématique offrait une autre issue, calculer la borne une fois avec std::sqrt, mais alors l’exactitude de la borne dépend de l’arrondi de la virgule flottante, et la division entière n’a pas ce problème.

La leçon « Nombres premiers et théorème fondamental de l’arithmétique », du cours Algèbre et géométrie I, démontre que tout entier strictement supérieur à 1 est un produit de nombres premiers d’une seule manière ; les divisions successives par essai sont la manière la plus directe de trouver ce produit, en divisant $n$ par chaque diviseur trouvé et en continuant avec le quotient.