Comment puis-je générer avec élégance des nombres premiers en Java à l'aide du tamis d'Eratosthène ?

Tamis d'Eratosthène en Java : Générez des nombres premiers avec élégance

Présentation

La génération de nombres premiers est un problème fondamental en informatique, avec une variété d'algorithmes parmi lesquels choisir. Parmi eux, le tamis d’Ératosthène est connu pour sa simplicité et son efficacité. Cet article fournit une implémentation Java élégante qui utilise le tamis d'Eratosthène pour générer les n premiers nombres premiers.

Tamis d'Ératosthène

Le Tamis d'Ératosthène est un algorithme probabiliste qui identifie les nombres premiers en éliminant de manière itérative les multiples de nombres premiers. Il initialise d'abord un tableau d'indicateurs booléens, chaque indicateur représentant un nombre jusqu'à la limite spécifiée. L'algorithme parcourt ensuite le tableau en commençant par le premier nombre premier 2 et marque tous ses multiples comme non premiers. Ce processus se poursuit jusqu'à ce que tous les nombres compris dans la limite aient été éliminés, ne laissant que les nombres premiers.

Mise en œuvre élégante

Une élégante implémentation Java du Tamis d'Eratosthène ressemble à ceci :

public static BitSet computePrimes(int limit) {
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 2; i * i <= limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j <= limit; j += i) {
                primes.set(j, false);
            }
        }
    }
    return primes;
}

Description

Cette implémentation crée un BitSet où chaque bit représente un nombre jusqu'à la limite spécifiée. Initialement, 0 et 1 sont marqués comme non premiers et tous les autres nombres sont marqués comme premiers.

La boucle externe parcourt le tableau en commençant par le premier nombre premier 2. Si le bit à la position actuelle est défini (indiquant qu'il est premier), la boucle interne marque tous les multiples de ce nombre premier comme non premiers. Ce processus se poursuit jusqu'à ce que tous les nombres dans la limite aient été éliminés.

Enfin, renvoyez le BitSet contenant les nombres premiers.

Conclusion

Cette implémentation Java du Sieve d'Eratosthène démontre l'élégance et la simplicité de l'algorithme. Il génère efficacement des nombres premiers et possède une structure claire et logique. Le code est optimisé pour les performances et la compréhension, ce qui en fait un outil précieux pour les programmeurs qui ont besoin d'un générateur de 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!