¿Hay algún algoritmo simple que pueda determinar si X es primo y no confundir a un simple programador mortal?

Question

He estado tratando de abrirme camino a través del Proyecto Euler, y he notado un puñado de problemas que le piden que determine un número primo como parte de él.

1) Sé que puedo simplemente dividir x por 2, 3, 4, 5, ..., raíz cuadrada de X y si llego a la raíz cuadrada, puedo (con seguridad) asumir que el número es primo . Lamentablemente, esta solución parece bastante klunky.

2) He examinado mejores algoritmos sobre cómo determinar si un número es primo, pero me confundo rápidamente.

¿Hay un algoritmo simple que pueda determinar si X es primo y no confundir a un simple programador mortal?

¡Muchas gracias!

Answer 1

El primer algoritmo es bastante bueno y se usa mucho en Project Euler. Si conoce el número máximo que desea, también puede investigar el tamiz de Eratosthenes.

Si mantiene la lista de números primos, también puede refinar el primer algo para dividirlo únicamente con números primos hasta la raíz cuadrada del número.

Con estos dos algoritmos (división y tamiz) debería ser capaz de resolver los problemas.

Editar: nombre fijo como se señala en los comentarios

Answer 2

Para Project Euler, tener una lista de los números primos es realmente esencial. Sugeriría mantener una lista que use para cada problema.

Creo que lo que estás buscando es Sieve of Eratosthenes.

Answer 3

El AKS primer algoritmo de prueba:

Input: Integer n > 1 


if (n is has the form ab with b > 1) then output COMPOSITE 

r := 2 
while (r < n) { 
    if (gcd(n,r) is not 1) then output COMPOSITE 
    if (r is prime greater than 2) then { 
     let q be the largest factor of r-1 
     if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break 
    } 
    r := r+1 
} 

for a = 1 to 2sqrt(r)log n { 
    if ((x-a)n is not (xn-a) (mod xr-1,n)) then output COMPOSITE 
} 

output PRIME; 

Answer 4

lo recomiendo Fermat's primality test. Es una prueba probabilística, pero es correcta sorprendentemente a menudo. Y es increíblemente rápido en comparación con el tamiz.

Answer 5

Aquí hay una optimización simple de su método que no es exactamente el Tamiz de Eratóstenes, pero es muy fácil de implementar: primero intente dividir X por 2 y 3, luego recorra j = 1..sqrt (X)/6 , tratando de dividir por 6 * j-1 y 6 * j + 1. Esto omite automáticamente todos los números divisibles por 2 o 3, obteniendo una aceleración de factor constante bastante buena.

Answer 6

Su derecho el simple es el más lento. Puedes optimizarlo de alguna manera.

Examine el uso del módulo en lugar de las raíces cuadradas. Mantenga un registro de sus números primos. solo necesita dividir 7 entre 2, 3 y 5, ya que 6 es un múltiplo de 2 y 3, y 4 es un múltiplo de 2.

Rslite mencionó el eranthenos sieve. Es bastante sencillo. Lo tengo en varios idiomas en casa. Agregue un comentario si desea que publique ese código más tarde.

---

Aquí está mi C++ one. Tiene mucho espacio para mejorar, pero es rápido en comparación con las versiones de idiomas dinámicos.

// Author: James J. Carman 
// Project: Sieve of Eratosthenes 
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers, 
// I mark them as 0, and ignoring them. 
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
#include <iostream> 

int main(void) { 
     // using unsigned short. 
     // maximum value is around 65000 
     const unsigned short max = 50000; 
     unsigned short x[max]; 
     for(unsigned short i = 0; i < max; i++) 
       x[i] = i + 2; 

     for(unsigned short outer = 0; outer < max; outer++) { 
       if(x[outer] == 0) 
         continue; 
       unsigned short item = x[outer]; 
       for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) { 
         unsigned int searchvalue = item * multiplier; 
         unsigned int maxValue = max + 1; 
         for(unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) { 
           if(x[maxIndex] != 0) { 
             maxValue = x[maxIndex]; 
             break; 
           } 
         } 
         for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) { 
           if(searchvalue > maxValue) 
             break; 
           if(x[searchindex] == searchvalue) { 
             x[searchindex] = 0; 
             break; 
           } 
         } 
       } 
     } 
     for(unsigned short printindex = 0; printindex < max; printindex++) { 
       if(x[printindex] != 0) 
         std::cout << x[printindex] << "\t"; 
     } 
     return 0; 
} 

Voy a arrojar el código de Perl y python que tengo tan pronto como lo encuentre. Son similares en estilo, solo menos líneas.

Answer 7

Veo que la prueba de primalidad de Fermat ya se ha sugerido, pero he estado trabajando con Structure and Interpretation of Computer Programs, y también dan el Miller-Rabin test (vea la Sección 1.2.6, problema 1.28) como otra alternativa. Lo he estado usando con éxito para los problemas de Euler.

Answer 8

Aquí es un simple test de primalidad en D (Marte Digital):

/** 
* to compile: 
* $ dmd -run prime_trial.d 
* to optimize: 
* $ dmd -O -inline -release prime_trial.d 
*/ 
module prime_trial; 

import std.conv : to; 
import std.stdio : w = writeln; 

/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 
bool 
isprime(Integer)(in Integer number) 
{ 
    /* manually test 1, 2, 3 and multiples of 2 and 3 */ 
    if (number == 2 || number == 3) 
    return true; 
    else if (number < 2 || number % 2 == 0 || number % 3 == 0) 
    return false; 

    /* we can now avoid to consider multiples 
    * of 2 and 3. This can be done really simply 
    * by starting at 5 and incrementing by 2 and 4 
    * alternatively, that is: 
    * 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...  
    * we don't need to go higher than the square root of the number */ 
    for (Integer divisor = 5, increment = 2; divisor*divisor <= number; 
     divisor += increment, increment = 6 - increment) 
    if (number % divisor == 0) 
     return false; 

    return true; // if we get here, the number is prime 
} 

/// print all prime numbers less then a given limit 
void main(char[][] args) 
{ 
    const limit = (args.length == 2) ? to!(uint)(args[1]) : 100; 
    for (uint i = 0; i < limit; ++i) 
    if (isprime(i)) 
     w(i); 
} 

Answer 9

Para generar todos los números primos menores que un límite Sieve of Eratosthenes (la página contiene variantes en 20 lenguajes de programación) es el más antiguo y el más simple solución.

En Python:

def iprimes_upto(limit): 
    is_prime = [True] * limit 
    for n in range(2, limit): 
     if is_prime[n]: 
      yield n 
      for i in range(n*n, limit, n): # start at ``n`` squared 
       is_prime[i] = False 

Ejemplo:

>>> list(iprimes_upto(15)) 
[2, 3, 5, 7, 11, 13] 

Answer 10

Para los números razonablemente pequeño, x% n para un máximo de sqrt (x) es terriblemente rápido y fácil de código.

mejoras simples:

de prueba 2 y sólo números impares.

prueba 2, 3 y múltiplos de 6 + o - 1 (todos los números primos distintos de 2 o 3 son múltiplos de 6 +/- 1, por lo que básicamente se salta todos los números pares y todos los múltiplos de 3

prueba sólo números primos (requiere calcular o almacenar todos los números primos hasta sqrt (x))

se puede utilizar el método de criba para generar rápidamente una lista de todos los números primos hasta un límite arbitrario, pero tiende a ser memoria intensiva. Puede utilizar los múltiplos de 6 truco para reducir el uso de memoria a 1/3 de un bit por número.

Escribí una clase principal simple (C#) que usa dos campos de bits para múltiplos de 6 + 1 y múltiplos de 6-1, luego hace una búsqueda simple ... y si el número que estoy probando está fuera de los límites del tamiz, entonces vuelve a caer en la prueba por 2, 3 y múltiplos de 6 +/- 1. Descubrí que generar un tamiz grande en realidad lleva más tiempo que calcular números primos sobre la marcha para la mayoría de los problemas de euler que he resuelto hasta ahora. ¡El principio de KISS ataca nuevamente!

Escribí una clase principal que utiliza un tamiz para precalcular primos más pequeños, luego se basa en la prueba por 2, 3 y múltiplos de seis +/- 1 para los que están fuera del rango del tamiz.

Answer 11

Estoy trabajando también a través de los problemas de Project Euler y de hecho acabo de terminar # 3 (por id) que es la búsqueda del mayor factor primo de un número compuesto (el número en el? Es 600851475143).

Miré toda la información sobre números primos (las técnicas de tamizado ya mencionadas aquí), y sobre la factorización de enteros en wikipedia y presenté un algoritmo de división de prueba de fuerza bruta que decidí que haría.

Así que como estoy haciendo los problemas de euler para aprender ruby ​​estaba buscando la codificación de mi algoritmo y tropecé con la biblioteca mathn que tiene un método Prime class y Integer class with a prime_division. cuan genial es eso.yo era capaz de obtener la respuesta correcta al problema con este fragmento de rubí:

require "mathn.rb" 
puts 600851475143.prime_division.last.first 

este fragmento da salida a la respuesta correcta a la consola. Por supuesto que terminé haciendo un montón de lectura y el aprendizaje antes de que me encontré con esta pequeña belleza, pensé que iba a compartir con todo el mundo ...

Answer 12

Teniendo en cuenta los siguientes hechos (desde MathsChallenge.net):

• Todos los números primos excepto 2 son impares.
• todos los primos mayores que 3 se puede escribir en la forma 6k - 1 o 6k + 1.
• No es necesario comprobar más allá de la raíz cuadrada de n

Ésta es la función de C++ que utilizo para relativamente pequeño n:

bool isPrime(unsigned long n) 
{ 
    if (n == 1) return false; // 1 is not prime 
    if (n < 4) return true; // 2 and 3 are both prime 
    if ((n % 2) == 0) return false; // exclude even numbers 
    if (n < 9) return true; //we have already excluded 4, 6, and 8. 
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3 

    unsigned long r = floor(sqrt(n)); 
    unsigned long f = 5; 
    while (f <= r) 
    { 
     if ((n % f) == 0) return false; 
     if ((n % (f + 2)) == 0) return false; 
     f = f + 6; 
    } 
    return true; // (in all other cases) 
} 

Probablemente pueda pensar en más optimizaciones propias.

Answer 13

Me gusta este código python.

def primes(limit) : 
    limit += 1 
    x = range(limit) 
    for i in xrange(2,limit) : 
     if x[i] == i: 
      x[i] = 1 
      for j in xrange(i*i, limit, i) : 
       x[j] = i 
    return [j for j in xrange(2, limit) if x[j] == 1] 

Una variante de esto se puede utilizar para generar los factores de un número.

def factors(limit) : 
    limit += 1 
    x = range(limit) 
    for i in xrange(2,limit) : 
     if x[i] == i: 
      x[i] = 1 
      for j in xrange(i*i, limit, i) : 
       x[j] = i 
    result = [] 
    y = limit-1 
    while x[y] != 1 : 
     divisor = x[y] 
     result.append(divisor) 
     y /= divisor 
    result.append(y) 
    return result 

Por supuesto, si tuviera en cuenta un lote de números, no volvería a calcular el caché; Lo haría una vez y buscaré en él.

Answer 14

otra manera en Python es:

import math 

def main(): 
    count = 1 
    while True: 
     isprime = True 

     for x in range(2, int(math.sqrt(count) + 1)): 
      if count % x == 0: 
       isprime = False 
       break 

     if isprime: 
      print count 


     count += 2 


if __name__ == '__main__': 
    main() 

Answer 15

sorprendido de que nadie ha presentado una versión de PHP, así que aquí está mi presentación:

function sieve_of_erathosthenes($max) { 

    // populate array 
    for ($i = 2; $i <= $max; $i++) { 
     $array[] = $i; 
    } 

    // sieve of eratosthenes algo 
    for ($i = 0, $j = count($array); $i < $j; $i++) { 
     $prime[] = $p = array_shift($array); 

     foreach ($array as $k => $v) { 
      if ($v % $p == 0){ 
       unset($array[$k]); 
       $j--; 
      } 
     }  
    } 

    return $prime; 

} 

Answer 16

no está optimizado pero es una función muy sencilla.

function isprime(number){ 

    if (number == 1) 
     return false; 

    var times = 0; 

    for (var i = 1; i <= number; i++){ 
     if(number % i == 0){ 
      times ++; 
     } 
    } 
     if (times > 2){ 
      return false; 
     } 

    return true; 
    }