Comment trouver efficacement des nombres premiers dans une plage donnée ?

Trouver des nombres premiers dans une plage donnée

En mathématiques, les nombres premiers sont des nombres entiers supérieurs à 1 qui ne sont divisibles par aucun autre nombre sauf 1 et eux-mêmes. Trouver des nombres premiers dans une plage spécifique peut être une tâche de programmation courante. Voici une explication détaillée de la façon d'aborder ce problème en JavaScript :

Approche par force brute

L'extrait de code fourni tente de trouver des nombres premiers entre 0 et 100 en utilisant une approche par force brute. Il vérifie si le nombre est divisible par un nombre compris entre 2 et 12 et renvoie le nombre si aucun diviseur n'est trouvé. Cependant, cette approche présente plusieurs inconvénients :

• Elle est inefficace, surtout pour les plages plus grandes.
• Il est difficile d'étendre pour trouver des valeurs premières pour des plages plus grandes.

Tamis d'Eratosthène

Un algorithme plus efficace pour trouver des nombres premiers est appelé le Tamis d'Eratosthène. Voici comment cela fonctionne :

1. Créez un tableau appelé sieve d'une longueur maximale de 1.
2. Initialisez tous les éléments du tableau sur false (en supposant que false signifie que le nombre est premier).
3. Parcourez le tableau de tamis de 2 à la racine carrée de max.
4. Pour chaque nombre premier i, marquez tous ses multiples comme non premiers en définissant sieve[i j] à vrai pour tout j de i j à max.
5. Après l'itération, les nombres non marqués dans le tableau de tamis sont des nombres premiers.

En JavaScript, le code pour le Tamis d'Ératosthène ressemble à ceci :

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

Cette approche a une complexité temporelle de O(n log log n), ce qui est bien plus efficace que l'approche par force brute.

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!