Pourquoi mon programme de recherche de nombres premiers ne produit-il aucun résultat et comment puis-je l'optimiser ?

Débogage d'un programme de nombres premiers avec une large plage

Un programmeur dépanne un programme conçu pour identifier les nombres premiers dans une plage variable large et longue. Le programme s'exécute sans erreur, mais ne produit aucune sortie. Voici le code problématique :

<code class="language-csharp">using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication16
{
    class Program
    {
        void prime_num(long num)
        {
            bool isPrime = true;
            for (int i = 0; i < num; i++) // Outer loop starts at 0!
            {
                isPrime = true;
                for (int j = 2; j < i; j++) // Inefficient inner loop
                {
                    if (i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine(i);
                }
            }
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            p.prime_num(100); // Example range
        }
    }
}</code>

Le problème principal réside dans la logique de la boucle imbriquée. La boucle externe commence à i = 0, identifiant à tort 0 comme un nombre premier. De plus, l’inefficacité de la boucle interne ralentit considérablement le processus pour les grandes portées. Il vérifie la divisibilité jusqu'à i-1, alors qu'il suffit de vérifier jusqu'à la racine carrée de i.

Une approche plus efficace utilise la méthode du tamis par division d'essai. Bien qu'une solution sur une seule ligne soit possible avec LINQ, elle est moins lisible. Une solution optimisée plus pratique est présentée ci-dessous :

<code class="language-csharp">using System;
using System.Collections.Generic;

public class PrimeFinder
{
    public static List<long> FindPrimes(long limit)
    {
        List<long> primes = new List<long>();
        bool[] isPrime = new bool[limit + 1];
        for (long i = 2; i <= limit; i++)
        {
            isPrime[i] = true;
        }

        for (long p = 2; p * p <= limit; p++)
        {
            if (isPrime[p])
            {
                for (long i = p * p; i <= limit; i += p)
                    isPrime[i] = false;
            }
        }

        for (long i = 2; i <= limit; i++)
        {
            if (isPrime[i])
            {
                primes.Add(i);
            }
        }
        return primes;
    }

    public static void Main(string[] args)
    {
        List<long> primes = FindPrimes(100); // Example range
        foreach(long p in primes)
        {
            Console.WriteLine(p);
        }
    }
}</code>

Ce code révisé utilise une approche basée sur le tamis d'Eratosthène pour de meilleures performances avec des plages plus larges. Il identifie et génère correctement les nombres premiers dans la limite spécifiée.

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!