Comment générer une quantité de nombres premiers définie par l'utilisateur?

Question

J'essaie de générer des nombres premiers en fonction de l'entrée de l'utilisateur. Voilà ce que j'ai jusqu'à présent, mais je ne peux pas l'air de le comprendre:

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. Parcourez-les à la main (cela ne prendra pas longtemps).

La raison pour laquelle vous obtenez vos résultats actuels est que toutes les itérations de la boucle externe (x < numberOfPrimes) ne produisent pas de résultat - elles omettent plusieurs itérations en raison de la structure de la boucle interne.

Ce que vous devez vraiment faire est de restructurer les boucles internes. Votre boucle la plus interne fonctionne correctement et devrait détecter les nombres premiers. Votre deuxième boucle, cependant, ne devrait tester que les numéros qui n'ont pas encore été testés. En outre, il devrait arrêter de faire une boucle une fois que vous avez trouvé un nombre premier.

Answer 2

Une fois les boucles triées, il suffit de vérifier b < sqrt (a), plus haut et vous auriez trouvé l'autre facteur en premier.

Answer 3

Ce que vous cherchez est appelé "Sieve of Eratosthenes." Comme je ne suis pas en train de faire les devoirs des gens, c'est le seul indice que je vais vous donner. L'algorithme est facilement trouvé sur Internet.

Answer 4

Vous devriez mieux structurer votre code, c'est vraiment désordonné comme vous le faites maintenant. Avoir une méthode IsPrime(int x) qui retourne vrai si x est premier et faux sinon.

Ensuite, pour générer numberOfPrimes nombres premiers, 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 of Eratosthenes, qui est une méthode beaucoup plus rapide. Pour savoir si un nombre x est premier ou non, essayez 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 vérifiez tout deux fois, et aussi vérifier les choses que vous ne devriez pas si vous êtes allé jusqu'à x/2 ou même x.

donc 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 pour ne pas vérifier les nombres pairs, car un nombre pair n'est jamais premier, à l'exception de 2 (à la fois dans le tamis et la méthode naïve). Traitez x = 2 comme un cas de bordure et commencez ensuite à vérifier tous les autres nombres (3, 5, 7, 9, 11 etc.)

Answer 5

Le nombre premier suivant (x) - est le nombre qui ne peut pas être divisé par tous les nombres premiers. s, cela s < = sqrt (x). Vous pouvez 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 6

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

copied from 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 7

1. Renommez 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 devrait être nommé requiredNumberOfPrimes. Quand je vois cette variable I Je me demande 'Est-ce combien il veut, ou combien il a trouvé?'). Deuxièmement, cela vous aidera à comprendre où vous allez mal. Les variables doivent être nommées logiquement en fonction de ce qu'elles représentent. Si vous ne pouvez pas expliquer ce que vos variables représentent (par exemple, un & b) alors vous ne 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 continuez jusqu'à ce que x soit égal ou supérieur à numberOfPrimes *. Chaque fois que vous parcourez la boucle, vous ajoutez 1 à x.

Etes-vous sûr que c'est ce que vous voulez faire? x semble représenter le nombre de nombres premiers que vous avez trouvés. Alors pourquoi ne pas l'incrémenter quand vous trouvez un premier, 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 regardez chaque 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 a à partir de zéro, et chaque fois que vous en boucle dans votre boucle a vous commencerez votre boucle b à partir de zéro. Donc, si x est 10, vous passez à travers une fois (a = 2), puis vous passez à nouveau à travers (a = 2, a = 3), puis vous passez à nouveau à travers (a = 2, a = = 3, a = 4), puis ...

3. Collectez vos résultats plutôt que de les écrire sur la console.

var primes = new List<int>(); 

C'est tellement simple. Lorsque vous trouvez un nombre premier, primes.Add(a);.Ensuite, vous savez combien de nombres premiers vous avez trouvés (primes.Count), vous pouvez utiliser la liste des nombres premiers pour déterminer efficacement le nombre premier suivant, et vous pouvez utiliser la liste plus tard si nécessaire.