How do you generate a certain amount of prime numbers?

Question

I am trying to generate primes based on user input. This is what I have so far, but I just can't figure it out:

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

You should be able to see why your results are wrong if you look at your loop structures. Go through them manually (this will not take much time).

The reason you get your current results is that not every iteration of the outer loop ( x < numberOfPrimes ) gives a result - it will skip a lot of iterations because of how the inner loop is structured.

What you really need to do is rebuild the inner loops. Your innermost loop works fine and should detect any prime numbers. However, your second cycle should only check numbers that have not yet been tested. In addition, he should stop the cycle as soon as you find a prime number.

Answer 2

You need to better structure your code, it’s really messy how you do it now. Have an IsPrime(int x) method that returns true if x is prime and false otherwise.

Then, to generate numberOfPrimes primes, you can do something like this:

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

Or use the Eratosthenes Sieve , which is a much faster method.

To find out if x prime or not, try all of its factors between 2 and Sqrt(x) . Why only Sqrt(x) ? Because if a*b = x , then x / b = a and x / a = b , then you will check everything twice, and also check what you do not need if you came up to x / 2 or even x .

So, something like this if you want to use the IsPrime(x) function:

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

But I suggest you use the sieve of Eratosthenes, as it is much faster. You can also optimize things so as not to check even numbers, since an even number is never prime, except for 2 (both in a sieve and in a naive method). Treat x = 2 as the edge of the edge, and then start checking every other number (3, 5, 7, 9, 11, etc.).

Answer 3

Once you select the loops, you should check only b <sqrt (a), any one above, and you would first find another factor.

Answer 4

What you are looking for is called the "Sieve of Eratosthenes." Since I do not do homework, this is the only key that I will give you. The algorithm is easy to find on the Internet.

Answer 5

The next prime number (x) is a number that cannot be divided into all primes s such that s <= sqrt (x). So you can use a function like

 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; } 

And how can you get prime numbers, for example

 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. Rename the variables.

Firstly, if this is homework, you will get poor grades (if your teacher is worth the salt) because you have meaningless variable names (yes, even numberOfPrimes is wrong and should be called requiredNumberOfPrimes ). When I see this variable I ask myself: "Is this how much he wants, or how much he found?" )

Secondly, it will help you understand where you are wrong. Variables should be logically named according to what they represent. If you cannot explain what your variables represent (e.g. a and b), you probably cannot explain what you are doing with them.

2. Look at your loops.

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

The for loop structure: (initialise; 'should I continue?'; 'each loop do this') . Therefore in your loop

• You continue until x becomes equal or numberOfPrimes *.
• Each time you go through the loop, you add 1 to x .

Are you sure this is what you want to do? x seems to represent the number of primes you found. So why not enlarge it when you find the stroke, and not when you start the cycle?

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

You look at every integer from 2 to x inclusive. And for each of these integers a you look at every integer between a and 2, inclusive. What are you going to do with these integers?

Each time you loop the top level loop (loop x ), you start loop a from scratch, and every time you loop a , you start your b loop from scratch.

So, if x is 10, you run once (a = 2), then you run again (a = 2, a = 3), then you run again (a = 2, a = 3, a = 4), then ...

3. Collect the results, not write them to the Console.

 var primes = new List<int>(); 

It is so simple. When you find the bar, primes.Add(a); . Then you know how many primes you found ( primes.Count ), you can use a list of primes to efficiently determine the next prime number, and you can use the list later if necessary.