Quelle est l'efficacité du tamis d'Ératosthène pour la génération de nombres premiers ?

Génération de nombres premiers la plus élégante : une approche tamisée

Face au défi de générer des nombres premiers, la recherche de l'élégance dans le code est une noble quête. Bien qu'il existe de nombreuses méthodes pour trouver des nombres premiers, le Tamis d'Ératosthène se distingue par sa simplicité et son efficacité.

Le Tamis d'Ératosthène fonctionne en créant un tableau booléen de longueur n, qui représente les nombres de 1 à n. Le tableau est initialement défini sur true pour tous les éléments, indiquant que chaque nombre est un nombre premier potentiel. L'algorithme parcourt ensuite le tableau, en commençant par le premier nombre non marqué, qui est 2. Il marque tous les multiples de 2 comme non premiers en définissant leurs valeurs dans le tableau sur false. Il passe ensuite au nombre non marqué suivant, 3, et répète le processus, marquant tous les multiples de 3 comme non premiers. Cela continue jusqu'au dernier nombre non marqué, √(n).

En utilisant cette approche, le tamis d'Eratosthène réduit considérablement le nombre de vérifications nécessaires pour trouver des nombres premiers, offrant ainsi une solution très efficace. Considérez l'implémentation Java suivante du Sieve :

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

Ce code crée un BitSet pour représenter les nombres de 1 à n et définit initialement tous les éléments sur true. Il parcourt ensuite le tableau, marquant tous les multiples de chaque nombre premier (en commençant par 2) comme non premiers. Le résultat est un BitSet où les seuls éléments définis sur true représentent les nombres premiers.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!