Tamiz Sundarama

La criba de Sundarama es un algoritmo determinista para encontrar todos los números primos hasta algún número entero . Diseñado por el estudiante indio Sundaram en 1934. $norte$

El algoritmo prevé la exclusión de una serie de números naturales del 1 a todos los números de la forma: $norte$

{\ estilo de visualización i + j + 2ij}

donde los índices recorren todos los valores naturales para los cuales , a saber, los valores de y Luego, cada uno de los números restantes se multiplica por 2 y se incrementa en 1. La secuencia resultante son todos los números primos en el intervalo . $i\leqslant j$ $i+j+2ij\leqslant N$ $i=1,\;2,\;\ldots ,\;\left\lpiso {\frac ({\sqrt {2N+1}}-1}2}\right\rpiso$ $j=i,\;i+1,\;\ldots ,\;\left\lfloor {\frac {Ni}{2i+1}}\right\rfloor .$ $[1,2N+1]$

Justificación

El algoritmo trabaja con números naturales impares mayores que uno, representados como , donde es un número natural. $2m+1$ $metro$

Si un número es compuesto , entonces por definición se puede representar como un producto de dos números impares mayores que uno, es decir: $2m+1$

2m+1=(2i+1)(2j+1)

, donde y son números naturales. Expandiendo los paréntesis, obtenemos que

i

j

{\ estilo de visualización 2m+1=4ij+2i+2j+1}

, o

{\ estilo de visualización 2m = 4ij + 2i + 2j}

, de lo que se sigue que

m=2ij+i+j

Así, si todos los números de la forma ( ) se excluyen de la serie de números naturales, entonces para cada uno de los números restantes el número debe ser primo. Y, a la inversa, si el número es primo, entonces el número no se puede representar en la forma y, por lo tanto, no se excluirá en el curso del algoritmo. $2ij+i+j$ ${\ estilo de visualización 1 \ leqslant i \ leqslant j}$ $metro$ $2m+1$ $2m+1$ $metro$ $2ij+i+j$ $metro$

#incluir <stdio.h> int principal () { intn ; _ escanear ( "%d" , & n ); booleano [ n + 1 ] ; para ( int yo = 1 ; yo <= norte ; yo ++ ) { a [ i ] = verdadero ; } para ( int yo = 1 ; 2 * yo * ( yo + 1 ) < norte ; yo ++ ) { int j_max = ( n - 1 ) / ( 2 * i + 1 ); para ( int j = i ; j <= j_max ; j ++ ) { a [ 2 * i * j + i + j ] = falso ; } } para ( int yo = 1 ; yo <= norte ; yo ++ ) { si ( un [ yo ]) { printf ( "%d" , 2 * i + 1 ); } } devolver 0 ; }

Ejemplo de implementación en python3.8

n = int ( entrada ()) sc = conjunto ( rango ( 1 , n + 1 )) para i en rango ( 1 , int (((( 2 * n + 1 ) ** 0.5 ) - 1 ) / 2 ) + 1 ): para j en rango ( i , ( n - 1 ) // ( 2 * i + 1 ) + 1 ): sc . eliminar ( i + j + 2 * i * j ) sc = ordenado ( i * 2 + 1 para i en sc ) imprimir ( sc )

Véase también

Enlaces

B. A. Kordemsky. ingenios matemáticos . — M .: GIFML, 1958.
Baxter, Andrew. Tamiz de Sundaram . Temas de la Historia de la Criptografía. MU Departamento de Matemáticas.