Comment pouvons-nous trouver efficacement tous les nombres premiers dans une plage donnée ?

Trouver des nombres premiers dans une plage donnée : une approche optimisée

Cet article aborde le défi consistant à identifier efficacement tous les nombres premiers dans une plage spécifiée. Un nombre premier, par définition, est un nombre naturel supérieur à 1 qui n'a pas de diviseur positif autre que 1 et lui-même.

Une approche erronée et sa correction

Une première tentative pour résoudre ce problème contenait une faille critique dans sa logique. Le code a itéré à partir de 0, incluant de manière incorrecte 0 et 1 comme nombres premiers potentiels, et a utilisé un test de primalité incorrect. La condition if (i != j && i % j == 0) identifie les nombres composés, pas les nombres premiers. La bonne approche consiste à vérifier si un nombre n'est pas divisible par un nombre autre que 1 et lui-même.

Solution optimisée à l'aide d'un tamis de division d'essai

Une méthode beaucoup plus efficace utilise un tamis à division d'essai. Cette approche exploite plusieurs optimisations clés :

1. Limite de racine carrée : Il suffit de tester la divisibilité jusqu'à la racine carrée du nombre cible. Si un nombre a un diviseur supérieur à sa racine carrée, il doit également avoir un diviseur plus petit que sa racine carrée.

2. Suppression de multiples :Une fois qu'un nombre premier est identifié, ses multiples sont supprimés de la liste candidate, réduisant considérablement le nombre de vérifications ultérieures.

3. Estimation par itération : Le code utilise une formule d'approximation (π(x) < 1,26 x / ln(x), où π(x) est la fonction de comptage des nombres premiers) pour estimer le nombre maximum d'itérations nécessaires, améliorant encore l'efficacité.

Le code optimisé (utilisant LINQ pour plus de concision) met en œuvre efficacement cette stratégie :

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);
</p>
<p>Cet algorithme raffiné offre une amélioration substantielle des performances par rapport à l'approche naïve, en particulier lorsqu'il s'agit de plages étendues.  L'utilisation de <code>Enumerable.Range, ToList, RemoveAll et Aggregate permet une mise en œuvre compacte et efficace.


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!