¿Cómo podemos excluir números no primos mientras generamos a través de 6n + 1 y 6n-1, donde n> 1? Por ejemplo, para n = 4 6n + 1, da 25 que no es primo, ¿cómo podemos excluirlo?

Answer 1

El patrón 6n + 1 / 6n-1 es una rueda mod-6, que omite múltiplos de 2 y 3. Puede usar una rueda mod-30 para omitir múltiplos de 5, mod-210 para 5 y 7, etc. Esto es muy útil, pero tiene rendimientos decrecientes y se vuelve difícil de manejar. Mi código tiene mod-30 en varios lugares, en parte porque obtenemos 8 candidatos por rueda que encaja perfectamente en un byte. Muchas implementaciones de tamiz rápido usan 30 o 210.

Esto generalmente se usa como un filtro muy rápido que le brinda un conjunto de candidatos. Por ejemplo, mis rutinas next_prime y prev_prime usan la rueda mod-30, por lo que con dos búsquedas de matriz omiten todos los múltiplos de 2, 3 y 5.

Los candidatos resultantes deben ejecutarse a través de una prueba de primalidad. Esto puede ser una división de prueba (divisibilidad de prueba hasta la raíz cuadrada de n), pruebas de Miller-Rabin (por ejemplo, Miller-Rabin determinista utilizando registros de bases SPRP de Miller-Rabin o conjuntos hash), BPSW o algo más.

Answer 2

Es una condición necesaria que cualquier número primo se pueda escribir como (6n + 1) o (6n-1), donde n es un número natural. Pero no es una condición suficiente. es decir, cualquier número que tenga la forma (6n + 1) o (6n-1) puede ser o no primo.