El tamiz Sundarama en la red está representado por una gran cantidad de fuentes de información breve. Sin embargo, decidí establecer lo que me gustaría leer al comienzo del estudio de los algoritmos de teoría de números.
El tamiz Sundarama es uno de los tres métodos más famosos para generar números primos. Ahora es habitual tratarlo como algo exótico debido a la poca complejidad computacional: O (N (logN)). Sin embargo, los asintóticos son asintóticos, y en la práctica, en el rango de tamizado de 32 bits, Atkin, por ejemplo, supera a Sundaram solo con una cuidadosa optimización.
Las implementaciones del tamiz Atkin, que circulan en Internet, no superan el tamiz Sundaram ni en términos de tiempo ni en eficiencia de memoria. Por lo tanto, el método Sundaram se puede utilizar como herramienta auxiliar en experimentos con algoritmos más avanzados.
El tamiz Sundarama encuentra todos los números primos en un rango dado de números naturales 3 ≤ n ≤ N "separando" los componentes. Sin pérdida de generalidad, el valor de N puede considerarse impar. Si N es par, entonces se garantiza que sea compuesto, y se puede excluir del rango de tamizado disminuyendo el valor del límite superior en uno.
El algoritmo se basa en el siguiente hecho. Cualquier número compuesto impar n se puede representar como el producto de dos números impares naturales mayores que uno:
(1)
n = (2 * i + 1) * (2 * j + 1),donde i y j son números naturales (cero no es un número natural). Es imposible imaginar un número primo n de esta forma, ya que de lo contrario significaría que n tiene divisores adicionales además de él y uno.
Escribimos el n impar en la forma 2 * m + 1, lo sustituimos en (1) y obtenemos la expresión para m:
(2)
m = 2 * i * j + i + j.Esta transformación conduce directamente a la idea del tamiz de Sundaram.
Para filtrar números compuestos de un intervalo dado, debe usar una matriz en la que un elemento con índice m sea representativo del número 2 * m + 1. Habiendo organizado la enumeración de los valores de las variables i y j, calcularemos el índice m de acuerdo con la fórmula (2), y en el correspondiente Los elementos de la matriz establecen la marca "número compuesto". Una vez completada la enumeración, se marcarán todos los números compuestos en el rango, y los primos se pueden seleccionar por la ausencia de una marca.
Queda por aclarar los detalles técnicos.
Según el razonamiento anterior, para representar el límite superior (impar) del rango de tamizado N, el índice m asume su valor máximo mmax = (N - 1) / 2. Esto determina el tamaño requerido de la matriz.
Enumeraremos los valores de i y j en dos ciclos: un bucle externo para enumerar los valores de i, y un bucle interno anidado para los valores de j.
El valor inicial del contador de bucle externo es i = 1. Dada la simetría completa de la aparición de las variables i y j en la expresión (2), para evitar cálculos duplicados repetidos, el ciclo interno debe comenzar con el valor j = i.
Encuentre el valor máximo para el contador de bucle externo imax ≥ i. Si el límite del rango N es un número compuesto impar, entonces con el valor i = imax, el bucle interno debe ejecutarse al menos una vez con el valor de su parámetro j = imax para eliminar N, y la expresión (2) tomará su valor máximo:
mmax = 2 * imax * imax + imax + imax,
imax ^ 2 + imax - mmax / 2 = 0.
Al resolver esta ecuación cuadrática, obtenemos:
imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.La restricción para el contador del ciclo interno jmax ≥ j se encuentra a partir de la desigualdad
mmax ≥ 2 * i * j + i + j , de donde obtenemos:
jmax = (mmax - i) / (2 * i + 1).Los valores de los límites superiores deben redondearse al valor entero más cercano, descartando la parte fraccionaria.
La siguiente es una lista de una clase de Cunda Sundaram muy simple que implementa el método descrito.
using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt;
Como parámetro al crear un objeto de tipo Sundaram, se indica el límite superior del rango de tamizado. Para tamizar, la clase usa una matriz de tipo BitArray. Esto aumenta el tiempo de ejecución, pero le permite cubrir todo el rango de 32 bits del tipo uint. El tamizado se realiza al acceder al método Sieve () desde el constructor de la clase. Después de su finalización, el campo dt contendrá el tiempo de ejecución del tamiz en segundos.
Al acceder a la propiedad NextPrime, secuencialmente, comenzando desde 3, en orden ascendente, se devolverán los números primos. Después de que se agoten todos los simples del rango, se devolverá el valor 0.