Finding Prime Numbers: Part 1

So - I got it into my head to create a function that would find prime numbers.

There was no real reason for this project - it was just one of those coding ear worms that bug you until you actually do something about it. 

So - after staring at a blank IDE for a while, I decided what I really wanted to do was create an app that would give me n number of prime numbers in a list. But first, I needed a way to test whether or not a number was prime.


Rules for optimization:

  1. Don't optimize.
  2. Optimize later.

I decided that the best way to go for this project would be to determine the next prime number from a given integer. That way, I could generate lists and other such nonsense. I settled on the following sequence:

public int nextPrime(int lastNo)
{
    int currentNo = lastNo;
    bool isNotPrime = true;     while (isNotPrime)
    {
        isNotPrime = false;
        currentNo++;
        for (int i = 2; i < currentNo; i++)
        {
            if (currentNo % i == 0)
            {
                isNotPrime = true;
                break;
            }
        }
        return currentNo;
    }
}

It's a fairly simple exercise, so let's quickly walk through it.

The premise of the function is that we want to find the next prime number, not whether the input number itself is prime:

  1. We create a copy of the input number (currentNo).

  2. We create a conditional check (is the number not prime?) and set to true. This is so we can pass into the first conditional.

  3. While the conditional is true (the number is not prime)

    1. Set the conditional to false.  We are setting the assumption that the number is indeed a prime.

    2. increment the currentNo value by 1.

    3. Create a for-loop to go through all of the numbers between 2 and the currentNo minus 1.

    4. If the modulus of currentNo divided by the increment value (i) equals 0, then the number cannot be prime, so we set the test flag as true and break from the loop. Otherwise, we continue iterating through the set range of numbers until we exhaust it, or we manage to change the flag.

  4. If the test flag is true, re-run the sequence until it is not.

  5. Return the first value that results in the for-loop not changing the test flag to true.
So - fairly elegant, but far from optimized. For single checks, this function preforms quite fast. But what if we want to find the next 100, 1000, 10000, or 1 million prime numbers in a sequence? There is quite a bit of room for optimization here, so we can give that a look.
(To be continued . . .)

This is where THE END begins.