How do you generate a user defined amount of prime numbers?

Question

I'm trying to generate prime numbers based on user input. This is what I have so far but I just can't seem to 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 quite easily if you look at your loop structures. Step through them by hand (it won't take long).

The reason that you are getting your current results is that not every iteration of the outer loop (x < numberOfPrimes) produces a result - it will skip quite a few iterations due to the way the inner loop is structured.

What you really need to do is restructure the inner loops. Your innermost loop works fine, and should detect any prime numbers. Your second loop, however, should only test numbers that haven't yet been tested. Also, it should stop looping once you find a prime number.

Answer 2

You should structure your code better, it's really messy the way you do it now. Have a method IsPrime(int x) which 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 Sieve of Eratosthenes, which is a much faster method.

To figure out if a number x is 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, So you would check everything twice, and also check things you shouldn't if you went 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's much faster. You can also optimize things so you don't check even numbers, since an even number is never prime, except for 2 (both in the sieve and the naive method). Treat x = 2 as an edge case and then start checking every other number (3, 5, 7, 9, 11 etc.)

Answer 3

What you are looking for is called "Sieve of Eratosthenes." As I'm not into doing people's homework, this is the only clue I'm going to give you. The algorithm is easily found on the internet.

Answer 4

The next prime number (x) - is the number which cant be devided by all primes s, that s<=sqrt(x). So you can use 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 than you can get primes like

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

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 6

1. Rename your variables.

Firstly, if this is homework you will get bad marks (if your teacher is worth his salt) because you have meaningless variable names (yes, even numberOfPrimes is wrong and should be named requiredNumberOfPrimes. When I see this variable I am asking myself 'Is this how many he wants, or how many he has found?').

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

2. Look at your loops.

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

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

• You are continuing until x is equal to or great than numberOfPrimes*.
• Each time you go through the loop you are adding 1 to x.

Are you sure this is what you want to do? x appears to represent the number of primes you have found. So why not increment it when you find a prime, rather than when you start a loop?

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

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

Every time you loop through your top-level loop (the x loop), you are going to start your a loop from scratch, and every time you loop through your a loop you will start your b loop from scratch.

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

3. Collect your results rather than writing them to Console.

var primes = new List<int>();

It's so easy. When you find a prime, primes.Add(a);. Then you know how many primes you have found (primes.Count), you can use the list of primes to efficiently determine the next prime, and you can use the list later on if required.

Answer 7

Once you do get ithe loops sorted out, you only have to check for b < sqrt(a), any higher and you would have found the other factor first.