¿Cómo puedo generar una lista de primos basada en la Criba de Eratóstenes?
Me refiero a excluir los números divisibles de antemano, lo cual es complicado para los números grandes.
Soy un aficionado a la teoría de números, pero estaba pensando...
Es fácil generar números no pares en base 2 (binaria): basta con hacer un conjunto de números naturales en los que el LSD (dígito menos significativo, o LSB - l.s. bit) sea 1 (no cero). Se trata de una criba de primos con números que 2 divide eliminados.
Ahora bien, si quisiera generar números que el 3 no divide en base 3: basta con hacer un conjunto de números naturales donde el LSD sea 1 o 2 (no cero). Esto es una criba de primos con números que 3 divide eliminados.
... para muchas bases, pero vamos a considerar sólo las bases 2 y 3 en este ejemplo.
¿Existe un algoritmo de conversión de bases u otra solución para permitir estos obvios "conjuntos de criba" (término inventado) simultáneamente - quizás construyendo un sistema numérico que sea obviamente divisible por 2 y por 3, en lugar de dos sistemas numéricos (uno obviamente divisible por 2, otro por 3)?
La parte agotadora de esto a considerar creo, si es que es posible (sin juego de palabras), es la conversión entre bases. Es decir, usar, en el algoritmo ingenuo, la multiplicación y la sustracción para cada dígito.
PD: Sé que es más eficiente ejecutar la prueba de primalidad probabilística sobre un número aleatorio, es decir, comprobar si es primo, pero me encantaría la idea de construir sistemas numéricos que generen fácilmente conjuntos de primos, ignorando los compuestos, ya que la probabilidad de que un número sea primo disminuye logarítmicamente como 1/ln(x) - es decir ¡es decir, p(# alrededor de 1e3) = 14% y p(# alrededor de 1e300) = 1%, por lo que la mayoría de la memoria desperdiciada cuando inicialmente la construcción de la criba de eratóstenes conjunto a menos que haya una manera de saltar por sistema de números!
Sé que esto es ridículo, pero no puedo entender por qué no funciona, o cómo podría hacerlo. Creo que tiene que ver con: https://en.wikipedia.org/wiki/Divisibility_rule#Beyond_30 lo que requiere conocer los factores primos de antemano, o conocer un algoritmo para encontrar la inversa módulo n (no existe ninguno).
