¿Hay alguna forma de encontrar los números primos hasta 1000 con menos de 200 cálculos?

Question

Utilizando un tamiz creado por las Tablas de Números Primos establecidas por la fórmula PN+(PNx6) para números generados por 6n+o-1, se necesitan 182 cálculos para identificar 170 números compuestos. Utilizar la Criba de Eratóstenes llevaría unos 1600 cálculos. Las tablas de números primos identifican todos los números compuestos de la lista de 332 números primos posibles:

5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161...

7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169...

Tabla de números primos para:

5 identifica los múltiplos de 5 con 67 cálculos (la Criba de E: 249)

7: 23 cálculos (el tamiz de E: 133)

11: 29 cálculos (el tamiz de E: 98)

13: 11 cálculos (el tamiz de E: 75)

17: 17 cálculos (el tamiz de E: 57)

19: 4 cálculos (el tamiz de E: 51)

23: 12 cálculos (el tamiz de E: 42)

29: 5 cálculos (el tamiz de E: 34)

31: 1 cálculos (el tamiz de E: 31)

41: 3 47: 3 53: 2 59: 2 cálculos (el tamiz de E:0)

71: 2 89: 1 101: 1 cálculos (el tamiz de E: 0)

107: 1 113: 1 131: 1 137: 1 cálculos (el Tamiz de E: 0)

2: 0 cálculos (el tamiz de E:499)

3: 0 cálculos (el tamiz de E: 332)

Cálculos totales:

Una criba utilizando tablas PN: 187 cálculos para encontrar 166 números primos identificando 166 números compuestos (10 de 11 duplicados de múltiplos de 5).

Criba de Eratóstenes: 1601 cálculos para hallar 168 números primos identificando 832 números compuestos (769 duplicaciones de cálculos)

Nota: Lo que realmente espero es algo de ayuda. He probado esto hasta 1411. No hay razón para creer que no iría a cualquier número. Parece que como maneja menos números y menos cálculos, usaría menos memoria. Si nos fijamos en las tablas y lo que he podido investigar hace que los números Primes aún más interesante para los niños que luego podría tomar más interés en las matemáticas. Hola, soy un chico que trabaja en una tienda de comestibles al que le gusta pensar en las cosas. Necesito ayuda. La gente no para de hablarme del Tamiz de Eratóstenes. He dado una comparación entre los 2 tamices. ¿Prefieres hacer 1600 cálculos o 187?

Puede comprobarlo en mi sitio web: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers

Answer 1

Lo que se busca es una función computacional que devuelva la lista de primos menores que 1000, y que trabaje de la forma más eficiente posible, sólo en ese problema.

Existen 168 primos entre 1 y 1000, por lo que cualquier método llevará al menos 168 operaciones, obviamente.

Supongamos que pudiéramos encontrar aproximadamente una lista de 13 números y otra lista disjunta de 13 números, de tal forma que al sumar los dos conjuntos de números primos se obtuvieran precisamente todos los primos, y no más que eso (sin compuestos; de lo contrario habría que hacer más pruebas para filtrarlos).

Lo que quiero decir es:

$$ A := \{0, 2, 6\} \\ B := \{5, 11, 17\} \\ A + B = \{ 5, 11, 17, 7, 13, 19, 23\} $$

Lo más probable es que puedas encontrar dos conjuntos de unos 13-20 elementos cada uno, de forma que al sumarlos obtengas tu lista. Los conjuntos serían entonces constantes en tu programa, y el programa que genera tu salida en menos de 200 operaciones, en realidad en 169 operaciones aritméticas (menos si se te permite incluir $B$ que podrían ser todos números primos si hay un $0$ incluido en $A$ ).

Ver:

Comprimir los primos mediante la suma