Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C

Test de primalité par divisions successives

Vérifiez si un entier est premier en testant les diviseurs possibles seulement jusqu’à sa racine carrée. En C, la condition `d <= n / d` permet de vérifier cette limite sans risquer un dépassement de capacité dû à une multiplication.

Version : C23; repository compiler flag, production runtime not attested

Syntaxe

for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }

Le test de primalité par divisions successives vérifie si n possède un diviseur autre que 1 et n. Rejetez d’abord n < 2, acceptez n == 2, puis rejetez tous les autres nombres pairs. Pour les candidats restants, ne testez que les valeurs impaires de d, à partir de 3. Si n % d == 0, le nombre est composé. Si la boucle ne trouve aucun diviseur, le nombre est premier.

Les diviseurs vont par paires : si n = a * b et que les deux facteurs sont supérieurs à 1, au moins l’un d’eux ne dépasse pas la racine carrée de n. La borne est incluse : pour 49, la boucle doit aussi tester 7.

Pour vérifier la borne des diviseurs sans dépassement de capacité, utilisez d <= n / d plutôt que d * d <= n. Lorsque n et d sont positifs, la division entière en C arrondit le quotient à l’entier inférieur : les deux conditions sont donc mathématiquement équivalentes. La première évite toutefois de calculer un produit qui pourrait dépasser la plage de valeurs de int et entraîner un comportement indéfini. Dans le pire des cas, l’algorithme effectue O(√n) essais et utilise O(1) d’espace mémoire supplémentaire.

Exemples

#include <stdio.h>

static int is_prime(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;

    for (int d = 3; d <= n / d; d += 2) {
        if (n % d == 0) return 0;
    }
    return 1;
}

int main(void)
{
    const int values[] = {-7, 0, 1, 2, 4, 9, 29, 49};
    for (size_t i = 0; i < sizeof values / sizeof values[0]; ++i) {
        printf("%d: %d\n", values[i], is_prime(values[i]));
    }
    return 0;
}

Résultat

-7: 0
0: 0
1: 0
2: 1
4: 0
9: 0
29: 1
49: 0

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources