•   Posted in: 
  • C#
So - I got it into my head to create a function that would find prime numbers. There was no real reason to do so - it was just one of those coding ear worms that bug you until you actually do something about it. 

After staring at a blank IDE for a while, I decided what I reallywanted to do was create an app that would give me n number of prime numbers in a list.

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;
        for (int i = 2; i < currentNo; i++)
            if (currentNo % i == 0)
                isNotPrime = true;
        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 currentNovalue by 1.
    3. Create a for-loop to go through all of the numbers between 2 and the currentNominus 1.
    4. If the modulus of currentNodivided 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 very fast. But what if we want to find the next 100, 1000, 10000, or 1 million prime numbers in a sequence?

(To be continued . . .)
Post comment