Tamiz de Eratóstenes más allá de O (n). Prueba

En los comentarios a una de las publicaciones anteriores sobre el tamiz de Eratóstenes, se mencionó este breve algoritmo de Wikipedia :

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. 

El algoritmo es simple, pero no para todos parece obvio. El problema principal es que no hay evidencia en Wikipedia, y el enlace a la fuente ( pdf ) contiene un algoritmo bastante diferente al anterior.

En esta publicación intentaré, espero, demostrar de manera accesible que este algoritmo no solo funciona, sino que también lo hace para la complejidad lineal.

Definiciones

$$$\ mathcal {P}$ - Muchos primos.
$$$lp (x)$ - mínimo divisor primo de un número: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - otros factores: $$$rd (x) = x / lp (x)$

Tenga en cuenta que todas las definiciones anteriores son para $$$x \ ge 2$ .

Algunas propiedades obvias de las funciones presentadas anteriormente, que se utilizarán más adelante:
$$$lp (a \ times b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

Prueba

Lema 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
Prueba : porque cualquier divisor $$$rd (x)$ también un divisor $$$x$ y $$$lp (x)$ no superior a ningún divisor $$$x$ entonces $$$lp (x)$ no supera ningún divisor $$$rd (x)$ incluyendo el más pequeño de ellos. El único problema con esta declaración es si $$$rd (x)$ no tiene divisores simples, pero esto solo es posible si $$$x \ in \ mathcal {P}$ , que se excluye en la condición del lema.
$$$\ cuadrado$

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

Porque $$$lp (x) \ veces rd (x) = x$ (por definición $$$rd ()$ ), si nos dieran mucho $$$E$ entonces podríamos calcular $$$lp ()$ para todos los números compuestos hasta n. Esto se hace, por ejemplo, mediante el siguiente algoritmo:

Algoritmo 2:

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

Tenga en cuenta que $$$\ vert E \ vert \ le n$ por lo tanto, el algoritmo 2 anterior funciona para la complejidad lineal.

Además, demostraré que el algoritmo 1 de Wikipedia en realidad solo itera sobre todos los elementos de este conjunto, porque puede parametrizarse de una manera diferente.

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

Lema 2 : $$$E = E '$
Prueba :

Dejar $$$(a, b) \ en E$ => $$$\ existe x \ notin \ mathcal {P}, \ 2 \ le x \ le n \ mid a = lp (x), b = rd (x)$ .

Por definicion $$$lp (), rd ()$ : $$$a \ in \ mathcal {P}$ , $$$a \ times b = x$ . Por Lemma 1, $$$a \ le lp (b)$ .
porque $$$rd (x) <x$ entonces $$$b <n$ .
Desde $$$x \ notin \ mathcal {P}$ , $$$b \ ge 2$ .
Además, por definición $$$E$ , $$$x \ le n$ por lo tanto $$$a \ times b \ le n$ .
Las 4 condiciones $$$E '$ cumplido significa $$$(a, b) \ en E '$ => $$$E \ subconjunto E '$ .

Dejar $$$(a, b) \ en E '$ . Dejar $$$x = a \ veces b$ .
Por definicion $$$E '$ , $$$a \ in \ mathcal {P}$ . Significa $$$a$ - división simple $$$x$ .
$$$lp (x) = lp (a \ times b) = min (lp (a), lp (b)) = min (a, lp (b)).$
Porque $$$a \ le lp (b)$ entonces $$$lp (x) = a.$ Significa $$$b = rd (x).$
Por definición $$$x = a \ times b \ le n.$ Obviamente también $$$x = a \ times b \ ge 2.$
Todas las condiciones para $$$E$ completado => $$$E '\ subconjunto E.$

Por lo tanto $$$E = E '.$
$$$\ cuadrado$

Ahora queda resolver los correctos $$$r$ y $$$p$ de la definición del conjunto $$$E '$ y aplique el Algoritmo 2. Esto es exactamente lo que hace el Algoritmo 1 (solo se usa la variable i en lugar de r). Pero hay un problema! Para ordenar todos los elementos de un conjunto $$$E '$ calcular $$$lp,$ necesitamos saber $$$lp,$ porque hay una condición en la definición $$$p \ le lp (r)$ .

Afortunadamente, este problema tiene el orden de clasificación correcto. Es necesario resolver $$$r$ en el bucle externo, y $$$p$ - En el interior. Entonces $$$lp (r)$ ya será calculado Este hecho queda demostrado por el siguiente teorema.

Teorema 1:
El algoritmo 1 admite la siguiente invariante: después de la iteración del bucle externo para i = k, todos los primos hasta k inclusive se resaltarán en pr. También se contará $$$lp ()$ para todos $$$x \ notin \ mathcal {P} \ mid x \ le n, \ rd (x) \ le k$ en la matriz de lp.

Prueba :
Probamos por inducción. Para k = 2, la invariante se verifica manualmente. El único primer 2 se agregará a la lista pr, porque la matriz lp [] se llena inicialmente con ceros. Además, el único número compuesto en el que $$$rd (x) \ le 2$ Es 4. Es fácil verificar que el bucle interno se ejecutará exactamente una vez (para n> 3) y ejecutará correctamente lp [4]: ​​= 2.

Ahora suponga que el invariante se cumple para la iteración i = k-1. Probemos que también será válido para la iteración i = k.

Para hacer esto, es suficiente verificar que el número i, si es primo, se agregará a la lista pr y $$$lp ()$ se contará para todos los números compuestos $$$x \ le n,$ incluyendo $$$rd (x) = i.$ Son estos números de la invariante para k que no están cubiertos por la invariante para k-1.

Si i es simple, entonces lp [i] será 0, porque la única operación de escritura en la matriz lp, que teóricamente podría calcular lp [i] (en la línea 6), siempre escribe en índices compuestos, porque p * i (para i> 1) - siempre compuesto. Por lo tanto, el número i se agregará a la lista de primos. Además, en la línea 3, se contará lp [i].

Si i es compuesto, al comienzo de la iteración lp [i] ya será calculado por el invariante para i = k-1, porque $$$rd (i) <i$ o $$$rd (i) \ le i-1,$ por lo tanto, caigo bajo la condición invariante en la iteración anterior. Por lo tanto, el número compuesto i no se agregará a la lista de primos.

Además, teniendo el lp [i] correcto y todos los primos hasta i inclusive, el bucle en las líneas 5-6 iterará sobre todos los elementos $$$(p, i) \ en E '$ en el que la segunda parte es i:

• $$$p \ en P,$ porque es de la lista pr
• $$$p \ le lp (i),$ por condición para detener el ciclo
• $$$p \ veces i \ le n,$ por condición para detener el ciclo
• $$$i <n,$ se sigue de $$$p \ veces i \ le n, \ p> 1$

Todos los primos necesarios en la lista pr son, porque solo números hasta $$$lp (i) \ le i$ . Por lo tanto, los valores de lp [] se calcularán para todos los números compuestos $$$x$ para que $$$rd (x) = i$ . Estos son exactamente todos los números que faltaban durante la transición de la invariante para k-1 a la invariante para k.

Por lo tanto, la invariante se cumple para cualquier i = 2..n.

$$$\ cuadrado$

Según el invariante del Teorema 1 para i = n, resulta que todos los números primos hasta n y todo lp [] se calculará mediante el algoritmo 1.

Además, dado que en las filas 5-6 se ordenan varios elementos del conjunto $$$E$ , entonces el bucle interno total no se ejecutará más $$$\ vert E \ vert <n$ operaciones La operación de verificación en el bucle se ejecutará sin problemas $$$\ vert E \ vert + n - 1 <2n$ veces ( $$$\ vert E \ vert$ veces devolverá verdadero y n-1 veces, para cada i, devolverá falso). Todas las operaciones restantes están anidadas en un ciclo en i de 2 a n.
Se deduce que la complejidad del algoritmo 1 es O (n).