La méthode du crible d'Ératosthène permet de trouver efficacement tous les nombres premiers inférieurs ou égaux à n.

Contrairement à la méthode naïve (tester chaque nombre individuellement), le crible d'Ératosthène améliore considérablement l'efficacité, avec une complexité temporelle de O(n log log n), ce qui est idéal pour les grands ensembles.

Principe fondamental

Éliminer les nombres composés et garder les nombres premiers.

1. Commencer par 2, marquer ce nombre comme premier.
2. Marquer tous les multiples de 2 comme non premiers.
3. Trouver le prochain nombre non marqué (ex: 3) et le considérer comme premier, puis marquer ses multiples.
4. Répéter jusqu'à atteindre la racine carrée de n.

Code principal

std::vector<int> findPrimes(int n)
{
    std::vector<bool> isPrime(n + 1, true); // tableau de marquage
    std::vector<int> primes;

    isPrime[0] = isPrime[1] = false; // 0 et 1 ne sont pas premiers

    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i])
        {
            primes.push_back(i); // i est un nombre premier

            if ((long long)i * i <= n)
            {
                for (int j = i * i; j <= n; j += i)
                {
                    isPrime[j] = false; // marquer les multiples de i comme non premiers
                }
            }
        }
    }

    return primes;
}

Détails d'optimisation

for (int j = i * i; j <= n; j += i)

• Commencer à partir de i² car les multiples plus petits ont déjà été marqués par des nombres premiers plus petits.
• Par exemple, les multiples de 2 tels que 4, 6, 8... peuvent être marqués à partir de 2²; 6 = 2*3 a déjà été marqué par 2.

(long long)i * i <= n

• Empêcher les débordements lors de la multiplication, surtout lorsque n est grand.

Exemple : n = 10

Initial : [T, T, T, T, T, T, T, T, T, T, T]  // 0~10
Devenant : [F, F, T, T, F, T, F, T, F, F, F]

Nombres premiers : 2, 3, 5, 7

Complexité temporelle et spatiale

• Complexité temporelle : O(n log log n)
• Complexité spatiale : O(n) (utilisé principalement pour le tableau de marquage)

Comparé à la méthode naïve, cette approche offre une amélioration significative. Elle peut gérer facilement n ≈ 10^6.

Domaines d'application

• Recherche de tous les nombres premiers dans une plage (comme la fonction d'Euler, les intervalles premiers).
• Création rapide d'une table des nombres premiers pour des opérations ultérieures (comme la division par essai, la factorisation).
• Utilisé souvent comme module de prétraitement dans plusieurs problèmes algorithmiques.

Réflexions personnelles

• Le crible est plus efficace et plus élégant que la méthode naïve, devenant un outil standard pour résoudre des problèmes liés aux nombres premiers.
• L'optimisation du point de départ à i*i est un principe clé, permettant d'éviter les marquages redondants.
• Lors de la première implémentation, faire attention à l'évitement des débordements, utiliser long long pour les multiplications.

Pistes d'apprentissage supplémetnaires

• Crible d'Ératothène linéaire : optimiser davantage à O(n).
• Crible par intervalle : rechercher les nombres premiers dans une plage [L, R] très grande.