[pharylon]

OK, so, I've been doing Project Euler problems lately, and as most of you probalby know, a lot of them have to do with primes. Now, I know all about the Sieve of Eratosthenes, but for my own purposes I decided I wanted to come up with my own algorithm to build a list of primes. I knew it wouldn't be as efficient, I was just doing it to do it.

Anyway, part of the code I ended up with was this:

long i = primeList[primeList.Count - 1];
                    bool foundPrime = false;
                    while (!foundPrime)
                    {
                        i += 2;
                        foundPrime = true;
                        foreach (long prime in primeList)
                        {
                            if (i % prime == 0)
                            {
                                foundPrime = false;
                                break;
                            }
                        }
                    }
                    primeList.Add(i);

What this does is it sets i to the highest discovered prime and then increments it by 2 in each loop. It checks if that number is a prime by seeing if it's evenly divisible by any previously discovered (lower number) primes. If it's not divisible by any prime numbers smaller than itself, we know it's prime, and we add it to the prime list.

Now, this algorithm works. So I don't need help with that... but it's ugly. I hate how I set the boolean flag to false to test for it, set it to true at the beginning of the loop, and then set it back to false if the number being tested turns out to not be prime.

If it was just this once, I wouldn't be bothered by it, but I've used this construction on a couple other problems too (not for primes, but other problems where I set a bool to false outside a loop, true at the beginning of it, and running some tests inside the loop and set the bool back to false if the tests fail). Anyway, I know there must be a more elegant way to phrase this... so, anyone want to tell me what it is?

This post has been edited by pharylon: 11 March 2013 - 06:51 PM

[Skydiver]

Here's one way to do it:

IEnumerable<int> GetPrimes()
{
    for (int p in primeList)
        yield return p;

    int i = primeList.Last();
    while (true)
    {
        while (!IsPrime(i))
            i += 2;
        primeList.Add(i);
        yield return i;
    }
}

bool IsPrime(i)
{
    foreach(int p in primeList)
        if (i % p == 0)
            return false;
    return true;
}

You'll have to make sure to prime the primeList with 2 and 3 at the very least, though.

This post has been edited by Skydiver: 11 March 2013 - 08:16 PM

[Momerath]

Why not just set it as true at the start, remove the ! test and remove the inner line where you set it to true?

[Skydiver]

Momerath, on 11 March 2013 - 11:16 PM, said:

Why not just set it as true at the start, remove the ! test and remove the inner line where you set it to true?

If he did that, he would end up with 9 being prime:

long i = primeList[primeList.Count - 1];    // assume i == 7
bool foundPrime = true;
while (foundPrime)
{
    i += 2;    // i == 9
    foreach (long prime in primeList)
    {
        if (i % prime == 0)    // 9 % 3 == 0
        {
            foundPrime = false;
            break;
        }
    }
}   // loop will terminate because foundPrime == false
primeList.Add(i);    // Oops! 9 is not prime.

[Momerath]

ignore me, no caffeine

This post has been edited by Momerath: 12 March 2013 - 06:12 AM

[pharylon]

I know it's late saying this, but thanks, I'd never seen yield before, and this was very informative (I ended up doing a lot of other reading after seeing that).