Comprender el tamiz de Atkin

Question

Estoy intentando construir un programa (en C++) que cuente los factores primos de un número dado para un problema del Proyecto Euler usando el Tamiz de Atkin, pero estoy teniendo problemas para entender algunas partes de el pseudocódigo en el artículo de Wikipedia .

He entendido lo que hace el algoritmo desde un punto de vista académico leyendo las secciones anteriores y posteriores al pseudocódigo, pero a la hora de ponerlo en práctica me estoy topando con un muro. Como referencia, aquí está el pseudocódigo:

// 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

No estoy seguro de por qué la raíz cuadrada de limit en lugar de utilizar la variable limit en sí mismo. Tampoco estoy seguro de por qué el bucle que removes composites by sieving está funcionando entre 5 y sqrt(limit) en lugar de 1 y limit .

Answer 1

Para la optimización, el algoritmo trata 2 y 3 como especiales, y como sabemos que 4 no es un primo, el último bucle comienza en 5.

Tampoco es necesario que te pases sqrt(limit) (una optimización crítica en todo algoritmo de búsqueda de primos) porque x² , y² y n² siempre será mayor que el propio límite (un número nunca puede ser divisible uniformemente por un número mayor que su raíz cuadrada sin ser divisible por un número menor).

Por supuesto, el bucle de cribado también debería incrementar al menos 2 en cada iteración, ya que ningún número par superior a 5 puede ser primo.

La página de la wiki también te dice que los primeros límites no están optimizados. Para la primera parte, $4x^2+y^2 \leq \mathrm{limit}$ Así que $y \leq \sqrt{\mathrm{limit}-4x^2}$ sería un límite más alto para el bucle interno (a la vez que se ahorra el coste computacional de comprobar que $n\leq\mathrm{limit}$ . Deberían aplicarse optimizaciones más agresivas para conseguir una implementación rápida.

No veo nada en su pregunta que pueda resultar difícil de aplicar.