¿Cómo comprobar si un gran número es primo?

Question

Es $31!+1$ un número primo?

Los números primos pueden escribirse como $6n+1$ o $6n-1$ forma.

$31!+1$ también puede escribirse como $6n+1$ pero no todos los números de la forma $6n+1$ es primordial.

¿Cómo procedo de manera eficiente?

Answer 1

La prueba más sencilla es comenzar con la división de prueba por primos pequeños. Su afirmación de que es $6n+1$ representa la división del juicio por $2$ y $3$ . Puedes seguir hasta que te canses. Entonces intenta El pequeño teorema de Fermat que dice que para $p$ primo y $a$ coprima a $p$ , $a^{p-1} \equiv 1 \pmod p$ Así que vea si $2^{8222838654177922817725562880000000} \equiv 1 \pmod {8222838654177922817725562880000001}$ Puede hacerlo rápidamente por ordenador si tiene el paquete adecuado. Si esta equivalencia falla, tienes un compuesto. Si pasa, comprueba otros primos pequeños. Si los supera todos, es casi seguro que tienes un primo.

Answer 2

Bueno, primero, puedes reducirlo un poco.

$31! + 1 = 8222838654177922817725562880000001$

Entonces, sólo hay que comprobar los números hasta la raíz cuadrada del número, ya que si un factor es mayor que la raíz cuadrada, el otro será menor.

$\sqrt{8222838654177922817725562880000001} = 90679869067935485.290072114674109180313966488379724733$

que si se redondea es $90679869067935485$ .

Lo que también es un número realmente grande. Entonces, por supuesto, sólo necesitas comprobar los factores primos del número (es decir, puedes comprobar el 5, pero no necesitas comprobar el 100). ¿Y después de eso?

Enchufar y beber es una forma de hacerlo, o puedes conectarlo a Wolfram|Alpha si te parece bien. También hay pruebas de primalidad (Actualizaré esta respuesta con más información).

Por último, a continuación se da un código en python que comprueba si un número es primo (no se enchufa $31! + 1$ pero la solución a eso):

# Python program to check if the input number is prime or not

# take input from the user
num = int(input("Enter a number: "))

# prime numbers are greater than 1
if num > 1:
   # check for factors
   for i in range(2,num):
       if (num % i) == 0:
           print(num,"is not a prime number")
           print(i,"times",num//i,"is",num)
           break
   else:
       print(num,"is a prime number")

# if input number is less than
# or equal to 1, it is not prime
else:
   print(num,"is not a prime number")

¡Por supuesto, 31! + 1 no es primo; es divisible por 257, entre otros números.

Espero que esto ayude.

Answer 3

Puede utilizar Prueba de primalidad AKS que se ejecuta en tiempo polinómico.

Te hace comprobar si el número es una potencia, y otros pasos bastante sencillos.

Aquí puedes encontrar implementaciones de este algoritmo en varios lenguajes de programación, por si quieres utilizarlo en un programa tuyo.