Prime numbers.

2    29 Oct 2016 16:29 by u/skruf

Being bored in a ride home for 3 hours, I wrote a simple prime number generator in C.

int main(int argc, char **argv)
{
    // 'a' will contain the number we'll check for prime.
    for (int a = 1; a <= 10000; ++a) {
        bool isPrime = true; // Assume by default that this is a prime number
        // 'b' will be the number we test against 'a' to see if it is divisable
        for (int b = 2; b < sqrt(a); ++b) {
            // If the number is divisable (no remainders) this number is not
            // a prime number. Break out, as there is no point carrying on.
            if ((a % b) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            printf("%d\n", a);
    }
    return 0;
}

Do any of you have a different approach? Any language goes.

Also, I am not, even remotely close, to a seasoned programmer. I just like to tinker around.

edit: added sqrt(a) for improving efficency

10 comments

4 u/Lopsid 29 Oct 2016 17:39

Made a little sieve of Eratosthenes. When a number is not prime, it's crossed out (set to 1).

int main()
{   int list[100] = {-1, -1};
    for(int prime = 2; prime <= 10; prime++)
    {   if(list[prime == 0])
        {   for(int cross = prime + prime; cross <= 99; cross += prime)
            {   list[cross] = 1;
            }
        }
    }
    for(int x=0; x <= 99; x++)
    {   printf("%2i: %2i\n", x, list[x]);
    }
    return 0;
}
2 u/tame 29 Oct 2016 16:52

As you've discovered, a brute force approach is trivial but runs very slowly, O(N^2) to find all primes up to N. There's a bunch of well known algorithms, like the Sieve of Eratosthenes, to speed it up. :)

0 u/skruf [OP] 29 Oct 2016 16:54

Thanks for the tip

1 u/PolishPandaBear 29 Oct 2016 17:55

Avoid square roots if possible. They cost a lot more in processing and you can easily replace the condition in your for loop with b*b < a.

Edit: Forgot there's no ^ operator in C.

0 u/Frenchgeek 29 Oct 2016 16:40

Don't you need to check until sqrt(a) at most?

0 u/skruf [OP] 29 Oct 2016 16:43

Apparently my approach gave me the desired results, but for not being the best maths guy, why should I do that?

0 u/Frenchgeek 29 Oct 2016 16:44

because that way you do far fewer checks per number, which make the whole thing far faster.

1 u/skruf [OP] 29 Oct 2016 16:46

Yeah I thought so aswell, the never ending discussion about making the most efficient code to a given problem!

0 u/Lopsid 29 Oct 2016 18:07

haha yes CPU cycles matter on the Mars rover.

0 u/rwbj 29 Oct 2016 17:57

Take a number, x, and imagine this number is composite.

Since it's composite there are two other numbers, n and m, that multiply together to produce x. What we want to know is what is the absolutely largest values, relative to x, that n and m can be. The reason we want to know the largest value is because that's as far as we need to check for divisibility. If the biggest they can be is 5, then we only need to run our for loop up to 5. And the reason we want them both to be large is because in cases of large_number * small_number we only need to check up to small number to get a hit. We want the worst case scenario which is where n and m are their max size. And the worst case scenario is where n and m are the same number so n*n = x. So what does n equal? sqrt(x).