Quelle est la méthode la plus élégante pour générer les N premiers nombres premiers ?

Une façon élégante de générer des nombres premiers

Le but est d'écrire une fonction generatePrimes(n) qui renvoie les premiers n nombres premiers. Il existe plusieurs façons d’obtenir cette fonctionnalité, chacune avec ses propres avantages et inconvénients. Cet article explore les méthodes les plus élégantes.

L'approche originale utilise généralement des boucles imbriquées pour vérifier les nombres premiers. Bien que cette approche fonctionne, elle manque d’élégance en raison de sa structure répétitive et imbriquée. Une approche plus élégante consiste à utiliser le tamis d'Ératosthène, qui a une complexité temporelle de O(n log log n).

Le Tamis d'Eratosthène fonctionne en créant un tableau booléen de taille n, avec tous les éléments initialement définis sur true. Les index de tableau représentent des nombres de 0 à n-1. L'algorithme définit d'abord les éléments aux index 0 et 1 sur false car ce ne sont pas des nombres premiers. Ensuite, pour chaque index i, il définit tous les multiples de i dans le tableau sur false. Ce processus est répété pour tous les indices jusqu'à la racine carrée de n. Les vrais éléments restants du tableau représentent des nombres premiers.

Voici une élégante implémentation Java du Tamis d'Eratosthène :

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

Ce code génère efficacement et élégamment les premiers n nombres premiers à l'aide du tamis d'Eratosthène. La complexité temporelle est O(n log log n), le code est concis et clair et il est idéal pour générer des 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!