Comment voulez-vous générer une quantité définie par l'utilisateur des nombres premiers?

Question

Je suis en train de générer des nombres premiers basés sur l'entrée d'utilisateur. Voilà ce que j'ai jusqu'à présent, mais je ne peux pas sembler figurer dehors:

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for

Answer 1

Vous devriez être en mesure de voir pourquoi vos résultats sont mauvais assez facilement si vous regardez vos structures en boucle. Étape à travers eux à la main (il ne prendra pas longtemps).

La raison pour laquelle vous obtenez vos résultats actuels est que chaque itération de la boucle extérieure (x < numberOfPrimes) produit un résultat - il sautera un bon nombre d'itérations en raison de la façon dont la boucle interne est structuré

.

Ce que vous avez vraiment besoin de faire est de restructurer les boucles internes. fonctionne votre boucle interne bien, et doit détecter les nombres premiers. Votre deuxième boucle, cependant, doit vérifier que des chiffres qui n'ont pas encore été testé. En outre, il devrait arrêter de boucler une fois que vous trouverez un nombre premier.

Answer 2

Vous devez structurer votre code mieux, il est salissant vraiment la façon dont vous le faites maintenant. Avoir une IsPrime(int x) méthode qui renvoie true si x est premier et false sinon.

Ensuite, pour générer des nombres premiers numberOfPrimes, vous pouvez faire quelque chose comme ceci:

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

Ou utilisez le Sieve de Eratosthène, qui est une méthode beaucoup plus rapide.

Pour savoir si un nombre x est premier ou pas, essayez de tous ses facteurs entre 2 et Sqrt(x). Pourquoi seulement Sqrt(x)? Parce que si a*b = x, puis x / b = a et x / a = b, donc vous tout vérifier deux fois, et vérifiez aussi des choses que vous ne devriez pas si vous êtes allé à x / 2 ou même x.

Alors quelque chose comme ça si vous voulez utiliser la fonction IsPrime(x):

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

Mais je vous suggère d'utiliser le tamis d'Eratosthène, car il est beaucoup plus rapide. Vous pouvez également optimiser les choses si vous ne cochez pas les nombres pairs, car un nombre pair est jamais premier, à l'exception de deux (à la fois dans le tamis et la méthode naïve). Traiter x = 2 comme un cas limite, puis commencer à vérifier chaque autre numéro (3, 5, 7, 9, 11, etc.)

Answer 3

Ce que vous cherchez est appelé « Crible d'Eratosthène. » Comme je ne suis pas en faire les devoirs des gens, c'est le seul indice que je vais vous donner. L'algorithme est facile à trouver sur Internet.

Answer 4

Le nombre premier (x) - est le nombre qui, que l'art cant être divisés par tous les nombres premiers s <= sqrt (x). Vous pouvez donc utiliser la fonction comme

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

Et que vous pouvez obtenir des nombres premiers comme

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

Answer 5

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

copiés à partir codethinked.com

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

Answer 6

1. Renommer vos variables.

Tout d'abord, si c'est des devoirs que vous obtiendrez de mauvaises notes (si votre professeur vaut son sel) parce que vous avez des noms de variables vides de sens (oui, même numberOfPrimes est faux et doit être nommé requiredNumberOfPrimes. Quand je vois cette variable, je demande moi-même est-ce combien il veut, ou combien il a trouvé?).

En second lieu, il vous aidera à comprendre où vous allez mal. Les variables doivent être logiquement nommés en fonction de ce qu'ils représentent. Si vous ne pouvez pas expliquer ce que vos variables représentent (par exemple a et b), vous pouvez probablement pas expliquer ce que vous faites avec eux.

2. Regardez vos boucles.

for (int x = 0; x < numberOfPrimes; x++)

La structure d'une boucle est (initialise; 'should I continue?'; 'each loop do this'). Par conséquent, dans votre boucle

• Vous x jusqu'à ce que continuiez est égale ou grande que numberOfPrimes *.
• Chaque fois que vous passez par la boucle que vous ajoutez 1 à x.

Êtes-vous sûr que c'est ce que vous voulez faire? x semble représenter le nombre de nombres premiers que vous avez trouvé. Alors pourquoi ne pas incrémenter quand vous trouvez une prime, plutôt que lorsque vous démarrez une boucle?

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

Vous êtes à la recherche à chaque entier compris entre 2 et x, y compris. Et pour chacun de ces entiers a, vous êtes à la recherche à tout entier entre a et 2 inclus. Qu'allez-vous faire avec ces entiers?

Chaque fois que vous boucle dans votre boucle de niveau supérieur (la boucle x), vous allez commencer votre boucle de a à partir de zéro, et chaque fois que vous en boucle dans votre boucle de a vous commencerez votre boucle de b à partir de zéro.

Donc, si x est 10, vous courez à travers une fois (a = 2), vous courez à travers un nouveau (a = 2, a = 3), vous courez à travers un nouveau (a = 2, a = 3 , a = 4), puis ...

3. Rassemblez vos résultats plutôt que de les écrire à la console.

var primes = new List<int>();

Il est si facile. Lorsque vous trouvez une prime, primes.Add(a);. Alors, vous savez combien de nombres premiers que vous avez trouvé (primes.Count), vous pouvez utiliser la liste des nombres premiers pour déterminer efficacement le prochain premier, et vous pouvez utiliser la liste plus tard si nécessaire.

Answer 7

Une fois que vous ne recevez pas des boucles ithe triés, il suffit de vérifier b