Quel est l'algorithme le plus élégant pour générer des nombres premiers ?

Génération de nombres premiers : une quête d'élégance

Les algorithmes efficaces et esthétiques sont très appréciés en programmation. Cet article explore des méthodes élégantes pour générer des nombres premiers, améliorant ainsi une approche initiale de base.

Au-delà des bases

Le code original (non présenté ici) offrait une méthode de génération principale fonctionnelle, mais inefficace. Plusieurs améliorations ont été proposées pour améliorer à la fois la vitesse et la lisibilité.

Itération améliorée

Les contributions de Peter Smit, jmservera et Rekreativc mettent en évidence les approches itératives améliorées. Ces méthodes affinent la boucle de vérification des amorçages pour une plus grande efficacité. (Remarque : l'extrait de code fourni est incomplet et manque de logique cruciale pour déterminer la primalité. Un exemple complet et fonctionnel serait nécessaire pour une comparaison appropriée.)

Le tamis d'Ératosthène : une solution classique

La mise en œuvre par Starblue du Tamis d'Eratosthène offre une solution élégante et efficace. Cet algorithme marque les multiples de nombres premiers comme composites, réduisant considérablement la surcharge de calcul.

<code class="language-java">public static List<Integer> computePrimes(int limit) {
    boolean[] isPrime = new boolean[limit + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}</code>

Approches alternatives

D'autres suggestions incluaient l'exploitation de Java BigInteger et nextProbablePrime pour la concision (dfa), l'utilisation de LINQ pour la génération paresseuse (Maghis), et la pré-génération et le stockage d'un grand nombre premier dans un fichier pour un accès rapide (darin) .

Conclusion

L'approche idéale dépend de l'application spécifique et des préférences du développeur. Le Tamis d'Eratosthène offre un solide équilibre entre efficacité et élégance pour de nombreux scénarios. Cependant, les méthodes alternatives offrent des options précieuses pour différents besoins et styles de codage.

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!