Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <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>
    singulars
    1. This table or related slice is empty.
    1. POC#: How to make Sieve of Atkin incremental
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCharles
    1. USjakber
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI see. Well, I do have an implementation of an Eratosthenes sieve (or possibly just a variation of it... suddenly became a bit unsure :p), that run fine, but it seems to slow down quite a bit after a while. I am using them to solve Project Euler problems, and when using the Eratosthenes one my solution to problem 10 takes 2 seconds or so, but with the Atkin one it takes less than 200 milliseconds. Could be my implementation that is completely wrong though, of course... :p
      singulars
      1. PO
      1. USSvish
    2. COSvish, your Sieve of Eratosthenes (SoE) is likely not a true version as per the question at [SoE in F#](http://stackoverflow.com/questions/12014224/when-generating-primes-in-f-why-is-the-sieve-of-erosthenes-so-slow-in-this-p) but rather a Trial Division (TD) (uses a modulus of all previously found primes to determine primality), where a C# version of my first F# program implementing the true SoE will calculate the primes up to two million as required for Euler Problem 10 in just a few 10's of milliseconds. Your version of SoA is better than TD but not better than a true SoE.
      singulars
      1. PO
      1. USGordonBGood
    3. CO@jakber, you should be careful about your conclusion in your last paragraph, as Berstein's highly optimized Sieve of Atkin (SoE) beat an equivalently optimized Sieve of Eratosthenes **over a particular sieving range**; however, the SoA inherently has a wheel factorization eliminating the factors of 2, 3, and 5 where the SoE is not limited to that and can include higher order factorization wheel eliminations - a highly optimized SoE using maximum wheel factorizing still beats the SoA as in [Kim Walisch's primesieve](https://code.google.com/p/primesieve/).
      singulars
      1. PO
      1. USGordonBGood
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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