Énoncé du Problème

Étant donné un entier n, retournez le nombre de nombres premiers strictement inférieurs à n.

Exemples

Entrée : n = 10
Sortie : 4
Explication : Les nombres premiers inférieurs à 10 sont 2, 3, 5, 7.

Entrée : n = 0
Sortie : 0

Entrée : n = 1
Sortie : 0

Introduction aux Méthodes de Crible

Pour compter efficacement les nombres premiers, plusieurs algorithmes de crible existent. Parmi eux, le crible naïf, le crible d'Eratosthène et le crible d'Euler (aussi appelé crible linéaire) sont couramment utilisés. Le crible d'Euler offre la meilleure complexité temporelle, atteignant O(n), contrairement aux autres méthodes qui sont moins optimales pour de grandes valeurs de n.

Crible Naïf

Cette approche vérifie pour chaque nombre i entre 2 et n s'il possède des diviseurs dans l'intervale [2, √i]. Si aucun diviseur n'est trouvé, i est considéré comme premier. La complexité temporelle est de O(n√n).

bool est_premier(int valeur) {
    for (int diviseur = 2; diviseur * diviseur <= valeur; diviseur++) {
        if (valeur % diviseur == 0) return false;
    }
    return true;
}

Crible d'Eratosthène

Cette méthode élimine progressivement les multiplse des nombres premiers identifiés, à partir de 2. Elle possède une complexité de O(n log log n).

const int TAILLE_MAX = 1000010;
bool est_composite[TAILLE_MAX];
vector<int> liste_premiers;

void initialiser_crible(int borne) {
    for (int idx = 0; idx <= borne; idx++) est_composite[idx] = false;
    est_composite[0] = est_composite[1] = true;
    for (int candidat = 2; candidat <= borne; candidat++) {
        if (!est_composite[candidat]) {
            liste_premiers.push_back(candidat);
            for (int multiple = candidat * candidat; multiple <= borne; multiple += candidat) {
                est_composite[multiple] = true;
            }
        }
    }
}
</int>

Crible d'Euler (Crible Linéaire)

Le crible d'Euler garantit que chaque nombre composé est éliminé par son plus petit facteur premier, assuarnt ainsi une complexité linéaire O(n). Il évite les calculs redondants présents dans le crible d'Eratosthène.

bool marquage_non_premier[5000001];
vector<int> nombres_premiers;

void appliquer_crible_euler(int limite) {
    for (int nombre = 2; nombre <= limite; nombre++) {
        if (!marquage_non_premier[nombre]) {
            nombres_premiers.push_back(nombre);
        }
        for (int premier : nombres_premiers) {
            if (premier * nombre > limite) break;
            marquage_non_premier[premier * nombre] = true;
            if (nombre % premier == 0) break;
        }
    }
}

int compter_premiers(int n) {
    int total = 0;
    appliquer_crible_euler(n);
    for (int i = 2; i < n; i++) {
        if (!marquage_non_premier[i]) total++;
    }
    return total;
}
</int>