Algoritmo para saber si un numero es primo
Lista de números primos
Números primosUn número primo es un número natural mayor que 1, que sólo es divisible por 1 y por sí mismo. Los primeros números primos son : 2 3 5 7 11 13 17 19 23 …..¡Atención lector! No dejes de aprender ahora. Hazte con todos los conceptos matemáticos importantes para la programación competitiva con el Curso de Matemáticas Esenciales para CP a un precio asequible para el estudiante. ¡Para completar tu preparación desde el aprendizaje de un lenguaje hasta el DS Algo y muchos más, consulta el Curso Completo de Preparación de Entrevistas.Algún dato interesante sobre los números primos (p – 1) ! ≡ -1 mod p
Cómo comprobar si un número es primo javascript
Si sólo tienes que saber si un determinado número es primo, hay varias pruebas de primos que aparecen en la wikipedia. Son probablemente el método más rápido para determinar si los números grandes son primos, especialmente porque pueden decirte si un número no es primo.
Si sólo necesita una manera de generar números primos muy grandes y no le importa generar todos los números primos < un número entero n, puede utilizar la prueba de Lucas-Lehmer para verificar los números primos de Mersenne. Un número primo de Mersenne tiene la forma de 2^p -1. Creo que la prueba de Lucas-Lehmer es el algoritmo más rápido descubierto para los números primos de Mersenne.
El polinomio (x-1)^P tendrá P+1 términos y puede ser encontrado usando la combinación. Por lo tanto, esta prueba se ejecutará en O(n) tiempo de ejecución, así que no sé lo útil que sería ya que usted puede simplemente iterar sobre i de 0 a p y la prueba para el resto.
¿Su problema es decidir si un número concreto es primo? Entonces necesitas una prueba de primalidad (fácil). ¿O necesita todos los primos hasta un número determinado? En ese caso, los tamices de primos son buenos (fáciles, pero requieren memoria). ¿O necesita los factores primos de un número? Esto requeriría la factorización (difícil para números grandes si realmente quieres los métodos más eficientes). ¿Qué tamaño tienen los números que estás buscando? ¿16 bits? ¿32 bits? ¿más grandes?
Algoritmo de prueba de primalidad
Para los números muy pequeños (menos de un millón), la división de prueba es la mejor manera: dividir por 2, 3, 5, y así sucesivamente hasta la raíz cuadrada del número. Si se encuentra un factor, el número es compuesto; en caso contrario, el número es primo.
Para números más grandes hay métodos mejores, pero la elección de uno de ellos depende del trabajo que estés dispuesto a realizar. Ahora se sabe que no hay BPSW-pseudoprimes por debajo de $2^{64}$, así que si usted puede escribir esa prueba (ver aquí para más detalles) entonces usted tiene una prueba muy rápida para la primalidad.
Hay muchos algoritmos diferentes para la prueba de primalidad. Ver la página de Wikipedia para una introducción y ver el libro de Henri Cohen «A course in computational algebraic number theory» para más detalles. Vea también las páginas de primos de Caldwell.
Existen varias soluciones de criba para encontrar números primos, la más antigua y famosa de las cuales es la criba de Eratóstenes. En general, son fáciles de programar y pueden, por ejemplo, encontrar todos los primos por debajo de 100.000 en unos pocos milisegundos en un procesador moderno.
Cómo comprobar si un número es primo java
El algoritmo se puede mejorar aún más observando que todos los primos son de la forma 6k ± 1, con la excepción de 2 y 3. Esto se debe a que todos los números enteros pueden expresarse como (6k + i) para algún número entero k y para i = -1, 0, 1, 2, 3 o 4; 2 divide a (6k + 0), (6k + 2), (6k + 4); y 3 divide a (6k + 3). Por lo tanto, un método más eficiente es comprobar si n es divisible por 2 o 3, y luego comprobar a través de todos los números de la forma 6k ± 1
Un número que no es primo será divisible por al menos un número primo. Por lo tanto, una forma de acelerar el algoritmo (a costa de la memoria) sería almacenar una lista de los números primos que ya se han encontrado, y sólo comprobar si alguno de ellos divide al número que se está comprobando en cada iteración.