Comment pouvons-nous générer efficacement des nombres premiers ?

Générer des nombres premiers avec élégance et efficacité

Dans le domaine de la programmation, trouver un moyen élégant et efficace de générer des nombres premiers est un classique défi. Explorons une approche qui établit un équilibre entre concision et performance.

Envisagez d'utiliser le théorème des nombres premiers, qui estime le nombre de nombres premiers inférieur ou égal à n comme pi(n) ≈ n / log(n) . Cette estimation fournit une limite supérieure sur la taille d'un tamis qui peut être utilisée pour identifier les nombres premiers.

La méthode du tamis, également connue sous le nom de Tamis d'Ératosthène, parcourt une plage de nombres et élimine tous les nombres non- prime en les marquant comme composites. Pour cette tâche, nous pouvons utiliser un BitSet pour représenter l'ensemble des nombres premiers, chaque bit correspondant à un nombre dans la plage.

Vous trouverez ci-dessous une implémentation Java de cette méthode de génération de nombres premiers élégante et efficace :

<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>

Cette méthode génère efficacement le premier million de nombres premiers en environ une seconde sur un ordinateur portable typique. Sa combinaison de précision et de rapidité en fait un outil précieux pour générer des nombres premiers dans divers scénarios informatiques.

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!