Peneira de Eratóstenes além de O (n). Prova

Nos comentários de um dos posts anteriores sobre a peneira de Eratóstenes, esse pequeno algoritmo da Wikipedia foi mencionado:

Algoritmo 1:

1:  i := 2, 3, 4, ...,  n: 2:  lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5:  p  pr  p ≤ lp[i]  p*i ≤ n: 6: lp[p*i] := p : lp -        n pr -     n. 

O algoritmo é simples, mas não para todos parecia óbvio. O principal problema é que não há evidências na Wikipedia, e o link para a fonte ( pdf ) contém um algoritmo bastante diferente do acima.

Neste post, tentarei, espero, ser possível provar que esse algoritmo não apenas funciona, mas também por complexidade linear.

Definições

$$$\ mathcal {P}$ - muitos números primos.
$$$lp (x)$ - divisor principal mínimo de um número: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - outros fatores: $$$rd (x) = x / lp (x)$

Observe que todas as definições acima são para $$$x \ ge 2$ .

Algumas propriedades óbvias das funções apresentadas acima, que serão usadas posteriormente:
$$$lp (a \ times b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

Prova

Lema 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
Prova : Porque qualquer divisor $$$rd (x)$ também um divisor $$$x$ e $$$lp (x)$ não é superior a qualquer divisor $$$x$ então $$$lp (x)$ não excede nenhum divisor $$$rd (x)$ incluindo o menor deles. O único problema com esta afirmação é se $$$rd (x)$ não possui divisores simples, mas isso só é possível se $$$x \ in \ mathcal {P}$ , que é excluído na condição do lema.
$$$\ quadrado$

Vamos $$$E = \ {(lp (x), rd (x)) \ vert \ forall x \ notin \ mathcal {P}, 2 \ le x \ le n \}$

Porque $$$lp (x) \ vezes rd (x) = x$ (por definição $$$rd ()$ ), se nos dessem muito $$$E$ então poderíamos calcular $$$lp ()$ para todos os números compostos até n. Isso é feito, por exemplo, pelo seguinte algoritmo:

Algoritmo 2:

 1:   (l,r)  E: 2: lp[l*r] := l; 

Note que $$$\ vert E \ vert \ le n$ portanto, o algoritmo 2 acima funciona para complexidade linear.

Além disso, vou provar que o algoritmo 1 da Wikipedia na verdade apenas repete todos os elementos desse conjunto, porque pode ser parametrizado de uma maneira diferente.

Vamos $$$E '= \ {(p, r) \ vert p \ in \ mathcal {P}, 2 \ le r <n, p \ le lp (r), p \ vezes r \ le n \}$

Lema 2 : $$$E = E '$
Prova :

Vamos $$$(a, b) \ em E$ => $$$\ existe x \ não em \ mathcal {P}, \ 2 \ arquivo x \ arquivo n \ meio a = lp (x), b = rd (x)$ .

Por definição $$$lp (), rd ()$ : $$$a \ in \ mathcal {P}$ , $$$a \ vezes b = x$ . Pelo lema 1, $$$a \ le lp (b)$ .
porque $$$rd (x) <x$ então $$$b <n$ .
Desde $$$x \ notin \ mathcal {P}$ , $$$b \ ge 2$ .
Além disso, por definição $$$E$ , $$$x \ le n$ portanto $$$a \ vezes b \ le n$ .
Todas as 4 condições $$$E '$ meios cumpridos $$$(a, b) \ em E '$ => $$$E \ subconjunto E '$ .

Vamos $$$(a, b) \ em E '$ . Vamos $$$x = a \ vezes b$ .
Por definição $$$E '$ , $$$a \ in \ mathcal {P}$ . Meios $$$a$ - divisão simples $$$x$ .
$$$lp (x) = lp (a \ vezes b) = min (lp (a), lp (b)) = min (a, lp (b))$
Porque $$$a \ le lp (b)$ então $$$lp (x) = a.$ Meios $$$b = rd (x).$
Por definição, $$$x = a \ times b \ le n.$ Obviamente também $$$x = a \ times b \ ge 2.$
Todas as condições para $$$E$ concluído => $$$E '\ subconjunto E.$

Portanto, $$$E = E '.$
$$$\ quadrado$

Agora resta escolher os corretos $$$r$ e $$$p$ da definição do conjunto $$$E '$ e aplique o algoritmo 2. É exatamente isso que o algoritmo 1 faz (apenas a variável i é usada em vez de r). Mas há um problema! Para classificar todos os elementos de um conjunto $$$E '$ calcular $$$lp,$ precisamos saber $$$lp,$ porque existe uma condição na definição $$$p \ le lp (r)$ .

Felizmente, esse problema contorna a ordem de classificação correta. É necessário resolver $$$r$ no loop externo e $$$p$ - por dentro. Então $$$lp (r)$ já será calculado. Este fato é comprovado pelo seguinte teorema.

Teorema 1:
O algoritmo 1 suporta a seguinte invariante: Após a iteração do loop externo para i = k, todas as primas até k inclusive serão destacadas em pr. Também será contado $$$lp ()$ para todos $$$x \ notin \ mathcal {P} \ meio x \ le n, \ rd (x) \ le k$ na matriz lp.

Prova :
Provamos por indução. Para k = 2, a invariante é verificada manualmente. O único primo 2 será adicionado à lista pr, porque a matriz lp [] é inicialmente preenchida com zeros. Além disso, o único número composto em que $$$rd (x) \ le 2$ - este é 4. É fácil verificar se o loop interno será executado exatamente uma vez (para n> 3) e executará corretamente lp [4]: ​​= 2.

Agora, suponha que o invariante seja válido para a iteração i = k-1. Vamos provar que também será válido para a iteração i = k.

Para fazer isso, basta verificar se o número i, se for primo, será adicionado à lista pr e se $$$lp ()$ será contado para todos os números compostos $$$x \ n,$ incluindo $$$rd (x) = i.$ São esses números da invariante para k que ainda não estão cobertos pela invariante para k-1.

Se i for simples, lp [i] será 0, porque a única operação de gravação no array lp, que teoricamente poderia calcular lp [i] (na linha 6), sempre grava em índices compostos, porque p * i (para i> 1) - sempre composto. Portanto, o número i será adicionado à lista de números primos. Além disso, na linha 3, lp [i] será contado.

Se i for composto, no início da iteração lp [i] já será calculado pela invariante para i = k-1, porque $$$rd (i) <i$ ou $$$rd (i) \ le i-1,$ portanto, eu cai sob a condição invariável na iteração anterior. Portanto, o número composto i não será adicionado à lista de números primos.

Além disso, tendo o lp [i] correto e todos os números primos até i inclusive, o loop nas linhas 5-6 iterará sobre todos os elementos $$$(p, i) \ em E '$ em que a segunda parte é i:

• $$$p \ em P,$ porque é da lista pr
• $$$p \ le lp (i),$ por condição para parar o ciclo
• $$$p \ vezes i \ le n,$ por condição para parar o ciclo
• $$$i <n,$ segue de $$$p \ vezes i \ le n, \ p> 1$

Todos os primos necessários na lista pr são, porque apenas números até $$$lp (i) \ le i$ . Portanto, os valores lp [] serão calculados para todos os números compostos $$$x$ para qual $$$rd (x) = i$ . Esses são exatamente todos os números que estavam faltando durante a transição da invariante para k-1 para a invariante para k.

Portanto, o invariante vale para qualquer i = 2..n.

$$$\ quadrado$

Pela invariante do Teorema 1 para i = n, todos os números primos até n e todos os lp [] serão calculados pelo algoritmo 1.

Além disso, como nas linhas 5-6, vários elementos do conjunto são classificados $$$E$ , o loop interno total não executará mais $$$\ vert E \ vert <n$ operações. A operação de verificação no loop será executada sem problemas $$$\ vert E \ vert + n - 1 <2n$ vezes ( $$$\ vert E \ vert$ vezes retornará verdadeiro e n-1 vezes, para cada i retornará falso). Todas as operações restantes são aninhadas em um ciclo em i de 2 para n.
Daqui resulta que a complexidade do algoritmo 1 é O (n).