Description: Compter le nombre de nombres premiers inférieurs à un nombre non négatif n.

Pour résoudre ce problème, nous utiliserons l'algorithme du Crible d'Ératosthène. Le principe est de marquer les nombres non-premiers en commençant par le premier nombre premier (2) et en élimniant tous ses multiples, puis en passsant au nombre premier suivant et en répétant le processus. Nous devons utiliser un tableau de booléens de taille n pour suivre quels nombres sont marqués comme non-premiers.

L'algorithme fonctionne comme suit :

1. Créer un tableau de booléens de taille n, initialisé à true
2. Marquer 0 et 1 comme non-premiers (false)
3. Parcourir les nombres de 2 à la racine carrée de n
4. Pour chaque nombre non marqué, marquer tous ses multiples comme non-premiers
5. Compter les nombres restant marqués comme true

Voici une implémentation en C++ :

class Solution {
public:
    int comptePremiers(int limite) {
        if (limite < 3) return 0;
        
        vector<bool> estPremier(limite, true);
        estPremier[0] = estPremier[1] = false;
        
        int resultat = 0;
        int racine = sqrt(limite);
        
        for (int i = 2; i <= racine; ++i) {
            if (estPremier[i]) {
                for (int j = i * i; j < limite; j += i) {
                    estPremier[j] = false;
                }
            }
        }
        
        for (int i = 0; i < limite; ++i) {
            if (estPremier[i]) ++resultat;
        }
        
        return resultat;
    }
};

Autres approches :

1. Optimisation mémoire<br></br>class Solution {  
public:  
    int comptePremiers(int n) {  
        if (n < 2)  
            return 0;  
            
        bool premiers[n];  
        memset(premiers, true, n*sizeof(bool));  
        premiers[0] = premiers[1] = false;  
      
        int total = 0;  
        int limite = sqrt(n);  
  
        for (int i = 2; i <= limite; i++) {  
            if (premiers[i]) {  
                for (int j = i*i; j < n; j += i) {  
                    premiers[j] = false;  
                }  
            }  
        }  
  
        for (int i = 0; i < n; i++) {  
            if (premiers[i]) {  
                total++;  
            }  
        }  
  
        return total;  
    }  
}; 

2. Approche avec compteur<br></br>class Solution {
public:
    int comptePremiers(int n) {
        if(n < 3)
            return 0;
            
        int *marqueur = new int[n];
        fill(marqueur, marqueur+n, 1);
        
        int compteur = n-2, limite = n/2;
        
        for(int i = 2; i <= limite; i++) {
            if(marqueur[i]) {
                for(int j = 2; i*j < n; j++) {
                    if(marqueur[i*j]) {
                        marqueur[i*j] = 0;
                        compteur--;
                    }
                }
            }
        }
        
        delete []marqueur;
        return compteur;
    }
};