Tamiz de Atkin

Dado un límite , imprime todos los números primos menores o iguales al límite dado.

Ejemplos: 

Entrada:   límite = 10
Salida: 2, 3, 5, 7

Entrada:   límite = 20
Salida: 2, 3, 5, 7, 11, 13, 17, 19 

Otros enfoques: los números primos hasta un límite se pueden generar utilizando otros algoritmos, como: 

• Criba de Eratóstenes : O(N*log(log(N)))
• Tamiz de Sundaram : O(N*log N)

Método de la criba de Atkin : La criba de Atkin es un algoritmo moderno para encontrar todos los números primos hasta un entero específico. 

Tamiz de Atkin vs Tamiz de Eratóstenes : 

En comparación con la antigua Criba de Eratóstenes , que marca múltiplos de números primos, hace un trabajo preliminar y luego marca múltiplos de cuadrados de números primos, por eso tiene una mejor complejidad asintótica teórica con Complejidad de (N / (log log N) )

Cómo funciona el algoritmo Tamiz de Atkin: 

El algoritmo Tamiz de Atkin funciona de manera similar al Tamiz de Eratóstenes para filtrar los números compuestos de una lista de números, pero este algoritmo funciona en términos de restos de módulo 60 . 

Entonces, primero asumimos que todos los números dentro del límite son compuestos y luego les aplicamos un filtro o un tamiz. Si durante cualquier filtro, el número parece ser primo, lo marcamos como primo y pasamos al siguiente número.

El filtro o tamiz en este algoritmo trabaja principalmente en 4 casos o capas:

• Caso 1: Si el límite es mayor que 2 o 3:
  • El algoritmo trata 2 y 3 como casos especiales y simplemente los agrega al conjunto de números primos para empezar.
• Caso 2: si 4x ² +y ² =n es impar y el resto módulo-12 es 1 o 5
  • Dado que todos los números con restos de módulo 60 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto de módulo 12 de 1 o 5. Por lo tanto, para este filtro también, tenemos que comprobar si el número es 1 o 5 cuando se toma módulo con 12.
  • Además, estos números son primos si y solo si el número de soluciones de 4x ² +y ² =n es impar y el número no tiene cuadrados. 
  • Un entero sin cuadrados es aquel que no es divisible por ningún cuadrado perfecto que no sea 1.
• Caso 3: si 3x ² +y ² =n es impar y el resto módulo-6 es 1
  • Todos los números con resto de módulo 60 7, 19, 31 o 43 tienen un resto de módulo 6 de 1. 
  • Estos números son primos si y solo si el número de soluciones de 3x ² + y ² = n es impar y el número no tiene cuadrados.
• Caso 4: si 3x ² -y ² =n es impar y el resto módulo-12 es 11
  • Todos los números con resto de módulo 60 11, 23, 47 o 59 tienen un resto de módulo 12 de 11. 
  • Estos números son primos si y solo si el número de soluciones de 3x ² – y ² = n es impar y el número no tiene cuadrados.
• Caso 5: Filtrado de todos los primos residuales que aún no se han encontrado
  • Debido al filtrado del algoritmo Tamiz de Atkin, puede haber algunos números primos que hayan sido descartados o no encontrados en los casos anteriores.
  • Entonces, para averiguarlos, seleccione todos los no primos dentro del límite y marque todos sus cuadrados como no primos.

Al final de todos los filtros anteriores, las posiciones en el Sieve con un valor verdadero serán la lista de números primos dentro del límite.

Ilustración del algoritmo Tamiz de Atkin:

Considere el límite como 20 y veamos cómo el algoritmo Sieve of Atkin genera números primos hasta 20:

Paso 0:  el estado de todos los números al principio es falso. Los números especiales son 2, 3 y 5, que se sabe que son primos.

Paso 1:  generar valores para las condiciones.  

Paso 2:  cambiar el estado según la condición.
Los valores anteriores de n en la tabla generada en el bucle x, y se probarán para condiciones de módulo.

• Columna 1: si (valor de la columna 1) % 12 == 1 o 5, cambie el estado del tamiz para ese número.
• Columna 2: si (valor de la columna 2) % 12 == 7, cambie el estado del tamiz para ese número.
• Columna 3: si (valor de la columna 3) % 12 == 11, cambie el estado del tamiz para ese número.

Nota: Note que estamos tomando mod con 12 en lugar de 60. Esto se debe a que si tomamos mod 60 entonces tenemos que considerar tantos r como 1, 13, 17, 29, 37, 41, 49 o 53 y para todos estos r, mod 12 es 1 o 5. (hecho solo para reducir el tamaño de la expresión)

Paso 3:  Comprobación de la condición libre de cuadrados: 
si algún número de nuestra lista es el cuadrado de cualquier número, elimínelo.

Paso 4: Crear una array de números primos cuyo estado sea verdadero. 
es decir, 2 3 5 7 11 13 17 19

Paso 5:  Imprima la salida en la pantalla.

Algoritmo de criba de Atkin paso a paso:

1. Cree una lista de resultados, completada con 2, 3 y 5.
2. Cree una lista de tamices con una entrada para cada entero positivo; todas las entradas en esta lista deben marcarse inicialmente como no principales.
3. Para cada número de entrada n en la lista de tamices, con resto de módulo sesenta r: 
   1. Si r es 1, 13, 17, 29, 37, 41, 49 o 53, voltea la entrada para cada posible solución a 4x ² + y ² = n.
   2. Si r es 7, 19, 31 o 43, voltea la entrada para cada posible solución a 3x ² + y ² = n.
   3. Si r es 11, 23, 47 o 59, cambie la entrada para cada posible solución a 3x ² – y ² = n cuando x > y.
   4. Si r es otra cosa, ignóralo por completo…
4. Comience con el número más bajo en la lista de tamices.
5. Tome el siguiente número en la lista de tamices, todavía marcado como primo.
6. Incluya el número en la lista de resultados.
7. Eleve el número al cuadrado y marque todos los múltiplos de ese cuadrado como no primos. Tenga en cuenta que no es necesario marcar los múltiplos que se pueden factorizar por 2, 3 o 5, ya que se ignorarán en la enumeración final de números primos.
8. Repita los pasos cuatro a siete.

A continuación se muestra la implementación del algoritmo anterior. 

// C++ program for implementation
// of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate primes
// till limit using Sieve of Atkin
void SieveOfAtkin(int limit)
{
    // Initialise the sieve array
    // with initial false values
    bool sieve[limit];
    for (int i = 0; i <= limit; i++)
        sieve[i] = false;
 
    // 2 and 3 are known to be prime
    if (limit > 2)
        sieve[2] = true;
    if (limit > 3)
        sieve[3] = true;
   
    /* Mark sieve[n] is true if one
       of the following is true:
    a) n = (4*x*x)+(y*y) has odd number of
       solutions, i.e., there exist
       odd number of distinct pairs (x, y)
       that satisfy the equation and
        n % 12 = 1 or n % 12 = 5.
    b) n = (3*x*x)+(y*y) has odd number of
       solutions and n % 12 = 7
    c) n = (3*x*x)-(y*y) has odd number of
       solutions, x > y and n % 12 = 11 */
    for (int x = 1; x * x <= limit; x++) {
        for (int y = 1; y * y <= limit; y++) {
 
            // Condition 1
            int n = (4 * x * x) + (y * y);
            if (n <= limit
                && (n % 12 == 1 || n % 12 == 5))
                sieve[n] ^= true;
 
            // Condition 2
            n = (3 * x * x) + (y * y);
            if (n <= limit && n % 12 == 7)
                sieve[n] ^= true;
 
            // Condition 3
            n = (3 * x * x) - (y * y);
            if (x > y && n <= limit
                && n % 12 == 11)
                sieve[n] ^= true;
        }
    }
 
    // Mark all multiples
    // of squares as non-prime
    for (int r = 5; r * r <= limit; r++) {
        if (sieve[r]) {
            for (int i = r * r; i <= limit; i += r * r)
                sieve[i] = false;
        }
    }
 
    // Print primes using sieve[]
    for (int a = 1; a <= limit; a++)
        if (sieve[a])
            cout << a << " ";
    cout << "\n";
}
 
// Driver program
int main(void)
{
    int limit = 20;
    SieveOfAtkin(limit);
    return 0;
}

// Java program for implementation
// of Sieve of Atkin
class GFG {
 
    static void SieveOfAtkin(int limit)
    {
        // 2 and 3 are known to be prime
        if (limit > 2)
            System.out.print(2 + " ");
 
        if (limit > 3)
            System.out.print(3 + " ");
 
        // Initialise the sieve array with
        // false values
        boolean sieve[] = new boolean[limit+1];
 
        for (int i = 0; i <= limit; i++)
            sieve[i] = false;
 
        /* Mark sieve[n] is true if one of the
        following is true:
        a) n = (4*x*x)+(y*y) has odd number
           of solutions, i.e., there exist
           odd number of distinct pairs
           (x, y) that satisfy the equation
           and    n % 12 = 1 or n % 12 = 5.
        b) n = (3*x*x)+(y*y) has odd number
           of solutions and n % 12 = 7
        c) n = (3*x*x)-(y*y) has odd number
           of solutions, x > y and n % 12 = 11 */
        for (int x = 1; x * x <= limit; x++) {
            for (int y = 1; y * y <= limit; y++) {
 
                // Main part of Sieve of Atkin
                int n = (4 * x * x) + (y * y);
                if (n <= limit
                    && (n % 12 == 1 || n % 12 == 5))
 
                    sieve[n] ^= true;
 
                n = (3 * x * x) + (y * y);
                if (n <= limit && n % 12 == 7)
                    sieve[n] ^= true;
 
                n = (3 * x * x) - (y * y);
                if (x > y && n <= limit
                    && n % 12 == 11)
                    sieve[n] ^= true;
            }
        }
 
        // Mark all multiples of squares as
        // non-prime
        for (int r = 5; r * r <= limit; r++) {
            if (sieve[r]) {
                for (int i = r * r; i <= limit;
                     i += r * r)
                    sieve[i] = false;
            }
        }
 
        // Print primes using sieve[]
        for (int a = 5; a <= limit; a++)
            if (sieve[a])
                System.out.print(a + " ");
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int limit = 20;
        SieveOfAtkin(limit);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python 3 program for
# implementation of
# Sieve of Atkin
 
def SieveOfAtkin(limit):
    # 2 and 3 are known
    # to be prime
    if limit > 2:
        print(2, end=" ")
    if limit > 3:
        print(3, end=" ")
 
    # Initialise the sieve
    # array with False values
    sieve = [False] * (limit + 1)
    for i in range(0, limit + 1):
        sieve[i] = False
 
    '''Mark sieve[n] is True if
    one of the following is True:
    a) n = (4*x*x)+(y*y) has odd
    number of solutions, i.e.,
    there exist odd number of
    distinct pairs (x, y) that
    satisfy the equation and
    n % 12 = 1 or n % 12 = 5.
    b) n = (3*x*x)+(y*y) has
    odd number of solutions
    and n % 12 = 7
    c) n = (3*x*x)-(y*y) has
    odd number of solutions,
    x > y and n % 12 = 11 '''
    x = 1
    while x * x <= limit:
        y = 1
        while y * y <= limit:
 
            # Main part of
            # Sieve of Atkin
            n = (4 * x * x) + (y * y)
            if (n <= limit and (n % 12 == 1 or
                                n % 12 == 5)):
                sieve[n] ^= True
 
            n = (3 * x * x) + (y * y)
            if n <= limit and n % 12 == 7:
                sieve[n] ^= True
 
            n = (3 * x * x) - (y * y)
            if (x > y and n <= limit and
                    n % 12 == 11):
                sieve[n] ^= True
            y += 1
        x += 1
 
    # Mark all multiples of
    # squares as non-prime
    r = 5
    while r * r <= limit:
        if sieve[r]:
            for i in range(r * r, limit+1, r * r):
                sieve[i] = False
 
        r += 1
 
        # Print primes
    # using sieve[]
    for a in range(5, limit+1):
        if sieve[a]:
            print(a, end=" ")
             
# Driver Code
limit = 20
SieveOfAtkin(limit)
 
# This code is contributed
# by Smitha

// C# program for implementation of Sieve
// of Atkin
using System;
 
class GFG {
 
    static void SieveOfAtkin(int limit)
    {
        // 2 and 3 are known to be prime
        if (limit > 2)
            Console.Write(2 + " ");
 
        if (limit > 3)
            Console.Write(3 + " ");
 
        // Initialise the sieve array with
        // false values
        bool[] sieve = new bool[limit + 1];
 
        for (int i = 0; i <= limit; i++)
            sieve[i] = false;
 
        /* Mark sieve[n] is true if one of the
        following is true:
        a) n = (4*x*x)+(y*y) has odd number
           of solutions, i.e., there exist
           odd number of distinct pairs
           (x, y) that satisfy the equation
           and    n % 12 = 1 or n % 12 = 5.
        b) n = (3*x*x)+(y*y) has odd number
           of solutions and n % 12 = 7
        c) n = (3*x*x)-(y*y) has odd number
           of solutions, x > y and n % 12 = 11 */
        for (int x = 1; x * x <= limit; x++) {
            for (int y = 1; y * y <= limit; y++) {
 
                // Main part of Sieve of Atkin
                int n = (4 * x * x) + (y * y);
                if (n <= limit
                    && (n % 12 == 1 || n % 12 == 5))
 
                    sieve[n] ^= true;
 
                n = (3 * x * x) + (y * y);
                if (n <= limit && n % 12 == 7)
                    sieve[n] ^= true;
 
                n = (3 * x * x) - (y * y);
                if (x > y && n <= limit
                    && n % 12 == 11)
                    sieve[n] ^= true;
            }
        }
 
        // Mark all multiples of squares as
        // non-prime
        for (int r = 5; r * r < limit; r++) {
            if (sieve[r]) {
                for (int i = r * r; i < limit;
                     i += r * r)
                    sieve[i] = false;
            }
        }
 
        // Print primes using sieve[]
        for (int a = 5; a <= limit; a++)
            if (sieve[a])
                Console.Write(a + " ");
        Console.WriteLine();
    }
 
    // Driver code
    public static void Main()
    {
        int limit = 20;
        SieveOfAtkin(limit);
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP program for implementation
// of Sieve of Atkin
 
function SieveOfAtkin($limit)
{
     
    // 2 and 3 are known
    // to be prime
    if ($limit > 2)
        echo 2 , " ";
    if ($limit > 3)
        echo 3 , " ";
 
    // Initialise the sieve array
    // with false values
    $sieve[$limit+1] = 0;
    for ($i = 0; $i <= $limit; $i++)
        $sieve[$i] = false;
 
    /* Mark sieve[n] is true if one
       of the following is true:
    a) n = (4*x*x)+(y*y) has odd number of
       solutions, i.e., there exist
       odd number of distinct pairs (x, y)
       that satisfy the equation and
       n % 12 = 1 or n % 12 = 5.
    b) n = (3*x*x)+(y*y) has odd number of
       solutions and n % 12 = 7
    c) n = (3*x*x)-(y*y) has odd number of
       solutions, x > y and n % 12 = 11 */
    for ($x = 1; $x * $x <= $limit; $x++)
    {
        for ($y = 1; $y * $y <= $limit; $y++)
        {
             
            // Main part of Sieve of Atkin
            $n = (4 * $x * $x) + ($y * $y);
            if ($n <= $limit
                && ($n % 12 == 1 || $n % 12 == 5))
                $sieve[$n] ^= true;
 
            $n = (3 * $x * $x) + ($y * $y);
            if ($n <= $limit && $n % 12 == 7)
                $sieve[$n] = true;
 
            $n = (3 * $x * $x) - ($y * $y);
            if ($x > $y && $n <= $limit
                && $n % 12 == 11)
                $sieve[$n] ^= true;
        }
    }
 
    // Mark all multiples of
    // squares as non-prime
    for ($r = 5; $r * $r <= $limit; $r++) {
        if ($sieve[$r]) {
            for ($i = $r * $r; $i <= $limit;
                             $i += $r * $r)
                $sieve[$i] = false;
        }
    }
 
    // Print primes
    // using sieve[]
    for ($a = 5; $a <= $limit; $a++)
        if ($sieve[$a])
            echo $a , " ";
    echo "\n";
}
 
    // Driver Code
    $limit = 20;
    SieveOfAtkin($limit);
 
// This code is contributed by nitin mittal.
?>

<script>
// Javascript program for implementation
// of Sieve of Atkin
 
function SieveOfAtkin(limit)
{
     
    // 2 and 3 are known
    // to be prime
    if (limit > 2)
        document.write(2 + " ");
    if (limit > 3)
        document.write(3 + " ");
 
    // Initialise the sieve array
    // with false values
    let sieve = new Array()
    sieve[limit+1] = 0;
    for (let i = 0; i <= limit; i++)
        sieve[i] = false;
 
    /* Mark sieve[n] is true if one
       of the following is true:
    a) n = (4*x*x)+(y*y) has odd number of
       solutions, i.e., there exist
       odd number of distinct pairs (x, y)
       that satisfy the equation and
       n % 12 = 1 or n % 12 = 5.
    b) n = (3*x*x)+(y*y) has odd number of
       solutions and n % 12 = 7
    c) n = (3*x*x)-(y*y) has odd number of
       solutions, x > y and n % 12 = 11
    */
    for (let x = 1; x * x <= limit; x++)
    {
        for (let y = 1; y * y <= limit; y++)
        {
             
            // Main part of Sieve of Atkin
            let n = (4 * x * x) + (y * y);
            if (n <= limit && (n % 12 == 1 ||
                                n % 12 == 5))
                sieve[n] ^= true;
 
            n = (3 * x * x) + (y * y);
            if (n <= limit && n % 12 == 7)
                sieve[n] = true;
 
            n = (3 * x * x) - (y * y);
            if (x > y && n <= limit &&
                            n % 12 == 11)
                sieve[n] ^= true;
        }
    }
 
    // Mark all multiples of
    // squares as non-prime
    for (let r = 5; r * r <= limit; r++) {
        if (sieve[r]) {
            for (i = r * r; i <= limit;
                            i += r * r)
                sieve[i] = false;
        }
    }
 
    // Print primes
    // using sieve[]
    for (let a = 5; a <= limit; a++)
        if (sieve[a])
            document.write(a , " ");
        document.write("<br>");
}
 
    // Driver Code
    let limit = 20;
    SieveOfAtkin(limit);
 
// This code is contributed by nitin gfgking
 
</script>

2 3 5 7 11 13 17 19 

 
Este artículo es una contribución de Anuj Rathore . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.