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

numeros primos del 1 al 100

Question

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

1) Sé que puedo 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 buscado mejores algoritmos sobre cómo determinar si un número es primo, pero me confundo rápidamente.

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

¡Muchas gracias!

Answer 1

Tu derecho, lo simple es lo 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 tamiz eranthenos . 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 ++ uno. 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;
}

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

Answer 2

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 3

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

Creo que lo que estás buscando es el tamiz de Eratóstenes .

Answer 4

Recomiendo la prueba de primalidad de Fermat . 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

Veo que la prueba de primalidad de Fermat ya ha sido sugerida, pero he estado trabajando a través de Estructura e Interpretación de Programas de Computadora , y también dan la prueba Miller-Rabin (ver Sección 1.2.6, problema 1.28) como otra alternativa. Lo he estado usando con éxito para los problemas de Euler.

Answer 6

Aquí hay una prueba de primalidad simple 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 7

El algoritmo de prueba principal AKS:

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 8

Para números razonablemente pequeños, x% n para hasta sqrt (x) es muy rápido y fácil de codificar.

Mejoras simples:

prueba 2 y números impares solamente.

prueba 2, 3, y múltiplos de 6 + o - 1 (todos los números primos que no sean 2 o 3 son múltiplos de 6 +/- 1, así que básicamente estás salteando todos los números pares y todos los múltiplos de 3

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

Puede usar el método de cribado para generar rápidamente una lista de todas las primarias hasta un límite arbitrario, pero suele requerir mucha memoria. Puede usar los múltiplos de 6 trucos 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, luego vuelve a caer en las pruebas 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 usa un tamiz para precalcular números primos más pequeños, luego confía en la prueba en 2, 3 y múltiplos de seis +/- 1 para los que están fuera del rango del tamiz.

Answer 9

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 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 mientras estoy haciendo los problemas de euler para aprender Ruby estaba buscando codificar mi algoritmo y encontré la biblioteca mathn que tiene una clase Prime y una clase Integer con un método prime_division . cuan genial es eso. Pude obtener la respuesta correcta al problema con este fragmento de rubí:

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

este fragmento muestra la respuesta correcta a la consola. por supuesto terminé haciendo una tonelada de lectura y aprendizaje antes de tropezar con esta pequeña belleza, solo pensé en compartirla con todos ...

Answer 10

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

• Todos los números primos, excepto 2, son impares.
• Todos los números primos superiores a 3 se pueden escribir en la forma 6k - 1 o 6k + 1.
• No necesita verificar más allá de la raíz cuadrada de n

Aquí está la función de C ++ que uso para n relativamente pequeña:

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 podrías pensar en más optimizaciones tuyas.

Answer 11

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 primos, también puede refinar el primer algo para dividirlo únicamente con primos hasta la raíz cuadrada del número.

Con estos dos algoritmos (divisor y tamiz) deberías ser capaz de resolver los problemas.

Editar : nombre fijo como se indica en los comentarios

Answer 12

Generar todos los números primos por debajo de un límite Tamiz de Eratóstenes (la página contiene variantes en 20 lenguajes de programación) es la solución más antigua y la más simple.

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 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 usar 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 estuviera factorizando un lote de números, no volvería a calcular el caché; Lo haría una vez y buscaré en él.

Answer 14

Otra forma 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 envió 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 simple.

    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;
    }