I'm attempting to construct a program (in C++) that will count the prime factors of a given number for a Project Euler problem using the Sieve of Atkin, but I'm having trouble understanding a few parts of the pseudocode on the Wikipedia article.
I've understood what the algorithm is doing from an academic point of view by reading the sections before and after the pseudocode, but when it comes to implementing it, I'm running up against a brick wall. For reference, here's the pseudocode:
// arbitrary search limit limit ← 1000000 // initialize the sieve is_prime(i) ← false, i ∈ [5, limit] // put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms for (x, y) in [1, √limit] × [1, √limit]: n ← 4x²+y² if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5): is_prime(n) ← ¬is_prime(n) n ← 3x²+y² if (n ≤ limit) and (n mod 12 = 7): is_prime(n) ← ¬is_prime(n) n ← 3x²-y² if (x > y) and (n ≤ limit) and (n mod 12 = 11): is_prime(n) ← ¬is_prime(n) // eliminate composites by sieving for n in [5, √limit]: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit} print 2, 3 for n in [5, limit]: if is_prime(n): print n
I'm unsure as to why the square root of limit
variable is being used, rather than limit
itself. I'm also unsure why the loop that removes composites by sieving
is running between 5
and sqrt(limit)
rather than 1
and limit
.