0
4

[–] Lopsid 0 points 4 points (+4|-0) ago  (edited ago)

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

0
2

[–] tame 0 points 2 points (+2|-0) ago 

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
0

[–] skruf [S] 0 points 0 points (+0|-0) ago 

Thanks for the tip

0
1

[–] PolishPandaBear 0 points 1 points (+1|-0) ago  (edited ago)

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
0

[–] Frenchgeek 0 points 0 points (+0|-0) ago  (edited ago)

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

0
0

[–] skruf [S] 0 points 0 points (+0|-0) ago 

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

0
0

[–] rwbj 0 points 0 points (+0|-0) ago 

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

0
0

[–] Frenchgeek 0 points 0 points (+0|-0) ago  (edited ago)

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