Édition pédagogique en français

Nombres premiers en C

Testez les diviseurs jusqu’à la racine carrée et traitez correctement les valeurs inférieures à deux.

Un nombre premier est un entier supérieur à un avec exactement deux diviseurs positifs. Zéro, un et les négatifs ne sont pas premiers. Un entier composé possède au moins un facteur ne dépassant pas sa racine carrée.

Écartez les pairs sauf deux, puis essayez les diviseurs impairs. Pour de grandes valeurs positives, divisor <= N / divisor évite le débordement de divisor * divisor. Arrêtez dès qu’un diviseur exact est trouvé.

Testez 1, 2, un carré comme 49 et un nombre premier. La division d’essai coûte O(sqrt(N)) en temps et O(1) en espace auxiliaire.

Code source

#include <stdio.h>
#include <stdbool.h>

bool is_prime_optimized(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Check factors 6k +/- 1 up to sqrt(n)
    for (int i = 5; (long long)i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    int test_numbers[] = {1, 2, 17, 25, 29, 49, 97, 100};
    int total = sizeof(test_numbers) / sizeof(test_numbers[0]);

    printf("--- Prime Number Verification ---\n");
    for (int i = 0; i < total; i++) {
        int val = test_numbers[i];
        printf("%3d -> %s\n", val, is_prime_optimized(val) ? "PRIME" : "NOT prime");
    }

    printf("\nPrimes between 1 and 50:\n");
    for (int i = 1; i <= 50; i++) {
        if (is_prime_optimized(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

Ouvrir dans le compilateur

Résultat attendu

--- Prime Number Verification ---
  1 -> NOT prime
  2 -> PRIME
 17 -> PRIME
 25 -> NOT prime
 29 -> PRIME
 49 -> NOT prime
 97 -> PRIME
100 -> NOT prime

Primes between 1 and 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.