Peneira Sundarama

A peneira Sundarama na rede é representada por um grande número de fontes de informações resumidas. No entanto, decidi declarar o que eu gostaria de ler no início do estudo dos algoritmos da teoria dos números.

A peneira Sundarama é um dos três métodos mais famosos para gerar números primos. Agora é costume tratá-lo como exótico por causa da baixa complexidade computacional: O (N (logN)). No entanto, os assintóticos são assintóticos e, na prática, na faixa de peneiração de 32 bits, Atkin, por exemplo, ultrapassa Sundaram apenas com otimização cuidadosa.

As implementações da peneira Atkin, que circulam na Internet, não superam a peneira Sundaram nem em termos de tempo nem em eficiência de memória. Portanto, o método Sundaram pode ser usado como uma ferramenta auxiliar em experimentos com algoritmos mais avançados.

A peneira Sundarama encontra todos os números primos em um determinado intervalo de números naturais 3 ≤ n ≤ N "peneirando" os componentes. Sem perda de generalidade, o valor de N pode ser considerado ímpar. Se N for par, é garantido que ele seja composto e pode ser excluído da faixa de peneiração, diminuindo o valor do limite superior em um.

O algoritmo é baseado no seguinte fato. Qualquer número composto ímpar n pode ser representado como o produto de dois números ímpares naturais maiores que um:

(1) n = (2 * i + 1) * (2 * j + 1),

onde iej são números naturais (zero não é um número natural). É impossível imaginar um número primo n nesta forma, pois, caso contrário, isso significaria que n possui divisores adicionais além de si mesmo e um.

Escrevemos o ímpar n na forma 2 * m + 1, substituí-lo em (1) e obtemos a expressão para m:

(2) m = 2 * i * j + i + j.

Essa transformação leva diretamente à ideia da peneira de Sundaram.

Para eliminar os números compostos de um determinado intervalo, você deve usar uma matriz na qual um elemento com o índice m é representativo do número 2 * m + 1. Depois de organizar a enumeração dos valores das variáveis ​​iej, calcularemos o índice m pela fórmula (2) e no correspondente elementos da matriz definem a marca "número composto". Após a conclusão da enumeração, todos os números compostos no intervalo serão marcados e os números primos podem ser selecionados pela ausência de uma marca.

Resta esclarecer os detalhes técnicos.

Com base no raciocínio anterior, para representar o limite superior (ímpar) da faixa de peneiração N, o índice m assume seu valor máximo mmax = (N - 1) / 2. Isso determina o tamanho necessário da matriz.

Enumeraremos os valores de iej em dois ciclos: um loop externo para enumerar os valores de i e um loop interno aninhado para os valores de j.

O valor inicial do contador de loop externo é i = 1. Dada a simetria completa da ocorrência das variáveis ​​iej na expressão (2), para evitar cálculos duplicados repetidos, o ciclo interno deve começar com o valor j = i.

Encontre o valor máximo para o contador de loop externo imax ≥ i. Se o limite do intervalo N for um número composto ímpar, então com o valor i = imax, o loop interno deve ser executado pelo menos uma vez com o valor do seu parâmetro j = imax para excluir N, e a expressão (2) terá seu valor máximo:

mmax = 2 * imax * imax + imax + imax,
imax ^ 2 + imax - mmax / 2 = 0.

Resolvendo essa equação quadrática, obtemos: imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.
A restrição para o contador do ciclo interno jmax ≥ j é encontrada na desigualdade
mmax ≥ 2 * i * j + i + j , de onde obtemos: jmax = (mmax - i) / (2 * i + 1).

Os valores dos limites superiores devem ser arredondados para o valor inteiro mais próximo, descartando a parte fracionária.

A seguir, é apresentada uma lista de uma classe Sundaram em C # muito simples que implementa o método descrito.

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

Como parâmetro ao criar um objeto do tipo Sundaram, é indicado o limite superior da faixa de peneiração. Para peneirar, a classe usa uma matriz do tipo BitArray. Isso aumenta o tempo de execução, mas permite cobrir todo o intervalo de 32 bits do tipo uint. A peneiração é realizada ao acessar o método Sieve () do construtor da classe. Após sua conclusão, o campo dt conterá o tempo de execução da peneira em segundos.

Ao acessar a propriedade NextPrime, sequencialmente, iniciando em 3, em ordem crescente, os números primos serão retornados. Depois que todos os simples do intervalo estiverem esgotados, o valor 0 será retornado.