StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I can try to explain what x and y does, but I don't think you can do what you ask without restarting the loops from the beginning. This is pretty much the same for any "sieve"-algorithm.</p> <p>What the sieve does is basically count how many different quadratic equations (even or odd) have each number as a solution. The specific equation checked for each number is different depending on what n % 12 is. </p> <p>For example, numbers <em>n</em> which have a mod 12 remainder of 1 or 5 are prime if and only if the number of solutions to 4*<em>x</em>^2+<em>y</em>^2=<em>n</em> is odd and the number is square-free. The first loop simply loops through all possible values of <em>x</em> and <em>y</em> that could satisfy these different equations. By flipping the isPrime[<em>n</em>] each time we find a solution for that <em>n</em>, we can keep track of whether the number of solutions is odd or even.</p> <p>The thing is that we count this for all possible <em>n</em> at the same time, which makes this much more efficient than checking one at the time. Doing it for just some <em>n</em> would take more time (because you would have to make sure that n >= lower_limit in the first loop) and complicate the second loop, since that one requires knowledge of all primes smaller than sqrt. </p> <p>The second loop checks that the number is square-free (has no factor which is a square of a prime number). </p> <p>Also, I don't think your implementation of the sieve of Atkin is necessarily faster than a straight-forward sieve of Eratosthenes would be. However, the fastest possible most optimized sieve of Atkin would beat the fastest possible most optimized sieve of Eratosthenes.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload