Comprensión de la función isPrime de Wikipedia, una función que determina si un número es primo

Question

Sé que hay varias preguntas sobre cómo determinar si un número es primo, pero ninguna de ellas me ayuda a entender esta aplicación concreta en Wikipedia, https://en.wikipedia.org/wiki/Primality_test Entiendo que los dos if declaraciones, no el for bucle. En concreto, ¿por qué incrementa i por 6 y por qué comprueba si n % (i+2) ¿igual a cero? Aquí está la implementación de JavaScript. Explícamelo como si tuviera 5 años por favor. Gracias de antemano.

function isPrime(n) {
    if (n <= 3) { return n > 1; }
    if (n % 2 == 0 || n % 3 == 0) { return false; }
    for (var  i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) { return false; }
    }
    return true;
}

Answer 1

Esto comprueba si $n$ es múltiplo de 2 ó 3 (al principio) y luego (bucle principal) si $n$ es múltiplo de 5,7,11,13,17,19,23,25,29,31, etc. $i$ va a subir por 6 a partir de las 5, y comprueba $i$ y $i+2$ . Así que la única pregunta es ¿por qué todos los primos están en esa lista? Es porque cada primo mayor que 3 debe dejar resto 1 o 5 cuando lo divides por 6. Así que hecho.

Answer 2

En $6n,6n+1,6n+2,6n+3,6n+4,6n+5$ los números $6n,6n+2,6n+3,6n+4$ son compuestos y no es necesario probarlos (puesto que sus propios factores ya se han probado antes). Sólo $5+6n$ y $5+6n+2=6n'+1$ permanecer ( $2$ de $6$ ).

---

Se puede generalizar, por ejemplo con $30n+k$ : sólo $30n+1,30n+7,30n+11,30+13,30+17,30n+19,30n+23,30n+29$ hay que probar ( $8$ de $30$ ).

Answer 3

Como respondieron los demás es simplemente una prueba para dividir por todos los números de la forma $6n+1$ y $6n+5$ . En $+=6$ en el bucle for hace que el coeficiente de $n$ sea $6$ . A partir de $5$ se puede demostrar que todos los números primos puede escribirse de la forma $6n+1$ o $6n+5$ . Hay muchos números que tienen la forma de 6n+1 $ or $ 6n+5$, pero todos los números primos pueden seguir escribiéndose de esa forma.

Esto se debe a que, por definición, los números primos no pueden escribirse en forma de $6n, 6n+2, 6n+3, 6n+4$ (tenga en cuenta que $6n+6$ puede escribirse como $6n'$ para que vuelva al ciclo)

Esto es así porque $6n+2, 6n+4$ son números pares y $6n+3$ es divisible por $3$ .