Search Voat (via searchvoat.co)

Submission Info

Posted by: skruf

Posting time: 1.9 years ago on

Last edit time: 1.9 years ago on

Archived on: 2/12/2017 1:51:00 AM

Traffic stats

Views: **455**

Score

SCP: **10**

**11** upvotes, **1** downvotes (**92%** upvoted it)

- system [O]

Cookies help us deliver our services. By using our services, you agree to our use of cookies.

## Sort: Top

[–] Lopsid 0 points 4 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).

[–] tame 0 points 2 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. :)

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

Thanks for the tip

[–] PolishPandaBear 0 points 1 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.

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

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

[–] skruf [S] 0 points 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?

[–] rwbj 0 points 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

bothto 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).[–] Frenchgeek 0 points 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.