Check Prime Number

Q: ¿Cuál es la complejidad temporal de comprobar si un número es primo?

La división por prueba hasta √n toma un tiempo de O(√n) y un espacio de O(1) . Para n hasta 2^31-1 , eso equivale a como máximo unas 46,000 divisiones, o 23,000 si omites los divisores pares. Probar todos los divisores hasta n-1 toma O(n) , unas dos mil millones de operaciones para la entrada más grande.

Q: ¿Por qué solo compruebas los divisores hasta la raíz cuadrada de n?

Los divisores vienen en pares d y n / d cuyo producto es n . Si ambos fueran mayores que √n , su producto sería mayor que n . Así que cada par tiene un elemento como máximo igual a √n , y si para entonces no aparece ningún divisor, n es primo.

Q: ¿Es 1 un número primo?

No. Un número primo tiene exactamente dos divisores distintos, 1 y él mismo, y 1 solo tiene uno. Excluir el 1 hace que la factorización en números primos de cada número entero sea única. Por eso, isPrime(1) devuelve false .

Q: ¿Hay una forma más rápida de comprobar si números muy grandes son primos?

Para un número de 32 bits, la división por prueba hasta √n es lo bastante rápida. Para números con docenas de dígitos, los programas usan la prueba de Miller-Rabin, que comprueba algunas potencias modulares en vez de probar divisores. Para enumerar todos los números primos hasta un límite, la criba de Eratóstenes es más eficiente que comprobar cada número por separado.

PrincipianteMatemáticas y simulación

+10

Un número primo es un número entero mayor que 1 cuyos únicos divisores son 1 y él mismo. Se te da un entero positivo n. Devuelve true si n es primo y false en caso contrario. El número 1 no es primo.

Función

isPrime(n: integer) → boolean

ninteger: el entero positivo que se va a probar
Devuelveboolean: verdadero si n es primo, falso en caso contrario

Restricciones

1 ≤ n ≤ 2³¹ - 1

Ejemplos

Entrada: n = 29
Salida: true
Explicación: Ninguno de 2, 3, 4 o 5 divide a 29, y 6 × 6 = 36 ya supera 29, así que no queda ningún divisor por encontrar. 29 es primo.

Entrada: n = 1
Salida: false
Explicación: Un número primo tiene exactamente dos divisores, 1 y él mismo. 1 solo tiene un divisor, así que la respuesta es false.

Entrada: n = 91
Salida: false
Explicación: 91 parece primo, pero 7 × 13 = 91. El divisor 7 aparece antes de que la búsqueda supere √91 ≈ 9.5.

+15 pruebas ocultas al enviar

Para ir más allá

Todo número primo mayor que 3 tiene la forma 6k-1 o 6k+1. ¿Puedes usar eso para probar solo un tercio de los divisores candidatos?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La definición dice que hay que descartar todos los divisores desde 2 hasta n-1, y para el número primo de entrada más grande eso supone más de dos mil millones de divisiones. Los divisores vienen en pares cuyo producto es n, y el menor de cada par es como máximo √n. Así que solo buscas hasta √n, como máximo unos 23,000 candidatos impares.

Prueba cada divisor

Correcto, pero no termina con las pruebas más grandes

Intuición

La definición te da el algoritmo. Un número n ≥ 2 es primo cuando ninguno de 2, 3, ..., n-1 lo divide. Prueba cada candidato d con n % d == 0 y devuelve false con el primero que lo divida. Para 91, el bucle prueba desde 2 hasta 6 y se detiene en 7.

Primero, maneja n < 2. Para n = 1, el rango de candidatos está vacío, así que el bucle nunca encontraría un divisor y consideraría primo a 1.

Los números compuestos suelen detenerse pronto, pero un número primo supera todas las pruebas, así que el bucle llega hasta el final. Para n = 2147483647, que es primo, eso supone alrededor de 2.1 × 10^9 divisiones, muchas más de las que se pueden hacer en unos pocos segundos.

Algoritmo

Si n < 2, devuelve false.
Recorre d desde 2 hasta n-1.
Si n % d == 0, devuelve false.
Después del bucle, devuelve true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

División por prueba hasta la raíz cuadrada

Intuición

Los divisores vienen en pares. Si d divide a n, también lo hace n / d, y los dos se multiplican para dar n. No pueden ser ambos mayores que √n, porque entonces su producto sería mayor que n. Así que, si n tiene algún divisor aparte de 1 y de sí mismo, tiene uno que es menor o igual que √n. Para 91, el par es 7 y 13, y 7 ≤ 9.5. Si nada hasta √n divide a n, tampoco lo hace nada por encima de ese valor.

Escribe el límite como d * d ≤ n en lugar de llamar a una función de raíz cuadrada. Se mantiene en números enteros, sin redondeo. El signo igual importa: 49 = 7 × 7, y su único divisor 7 está exactamente en √49.

También puedes omitir la mitad de los candidatos. Trata 2 por separado: un n par es primo solo cuando es 2. Después, un n impar solo tiene divisores impares, así que empieza en 3 y avanza de 2 en 2. Para n = 2147483647, el bucle ahora se ejecuta unas 23,000 veces en lugar de 2.1 × 10^9.

Algoritmo

Si n < 2, devuelve false.
Si n es par, devuelve si n == 2.
Empieza d en 3 y repite mientras d * d ≤ n, usando un tipo de 64 bits para d.
Si n % d == 0, devuelve false. De lo contrario, suma 2 a d.
Después del bucle, devuelve true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Errores comunes y casos límite

La idea cabe en una línea. Los errores aparecen en los límites: las entradas más pequeñas y el último divisor.

Devolver true para 1. Tiene un divisor, no dos, así que no es primo.
Rechazar 2 porque es par. Comprueba n == 2 antes de descartar los números pares.
Usar un bucle mientras d * d < n en lugar de ≤. Así, los cuadrados de números primos como 9, 49 y 2147117569 = 46337² pasan como primos.
Desbordamiento en d * d. En un int de 32 bits, 46341 × 46341 = 2147488281 no cabe y se desborda hasta convertirse en un número negativo, así que la comprobación sigue pasando y el bucle continúa mucho más allá de √n. Usa un tipo de 64 bits para d, o compara d ≤ n / d en su lugar.
Obtener el límite de una sqrt de punto flotante y truncarlo. Un double es exacto para todos los valores de n aquí, pero en las entradas de 64 bits el redondeo puede dar un valor una unidad por debajo de la raíz verdadera y omitir el único divisor que importa. d * d ≤ n no tiene ese riesgo.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de comprobar si un número es primo?

La división por prueba hasta √n toma un tiempo de O(√n) y un espacio de O(1). Para n hasta 2^31-1, eso equivale a como máximo unas 46,000 divisiones, o 23,000 si omites los divisores pares. Probar todos los divisores hasta n-1 toma O(n), unas dos mil millones de operaciones para la entrada más grande.

¿Por qué solo compruebas los divisores hasta la raíz cuadrada de n?

Los divisores vienen en pares d y n / d cuyo producto es n. Si ambos fueran mayores que √n, su producto sería mayor que n. Así que cada par tiene un elemento como máximo igual a √n, y si para entonces no aparece ningún divisor, n es primo.

¿Es 1 un número primo?

No. Un número primo tiene exactamente dos divisores distintos, 1 y él mismo, y 1 solo tiene uno. Excluir el 1 hace que la factorización en números primos de cada número entero sea única. Por eso, isPrime(1) devuelve false.

¿Hay una forma más rápida de comprobar si números muy grandes son primos?

Para un número de 32 bits, la división por prueba hasta √n es lo bastante rápida. Para números con docenas de dígitos, los programas usan la prueba de Miller-Rabin, que comprueba algunas potencias modulares en vez de probar divisores. Para enumerar todos los números primos hasta un límite, la criba de Eratóstenes es más eficiente que comprobar cada número por separado.

Python

def isPrime(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 29

Esperado

true