Algoritmo rápido para encontrar números primos?

Question

Primero de todo - Revisé mucho en este foro y no he encontrado algo suficientemente rápido. Intento hacer una función que me devuelva los números primos en un rango específico. Por ejemplo, hice esta función (en C#) usando el tamiz de Eratóstenes. Probé también tamiz de Atkin pero el Eratóstenes se ejecuta más rápido (en mi aplicación):

public static void SetPrimesSieve(int Range) 
    { 
     Primes = new List<uint>(); 
     Primes.Add(2); 
     int Half = (Range - 1) >> 1; 
     BitArray Nums = new BitArray(Half, false); 
     int Sqrt = (int)Math.Sqrt(Range); 
     for (int i = 3, j; i <= Sqrt;) 
     { 
      for (j = ((i * i) >> 1) - 1; j < Half; j += i) 
       Nums[j] = true; 
      do 
       i += 2; 
      while (i <= Sqrt && Nums[(i >> 1) - 1]); 
     } 
     for (int i = 0; i < Half; ++i) 
      if (!Nums[i]) 
       Primes.Add((uint)(i << 1) + 3); 
    } 

Se extiende alrededor de dos veces más rápido que los códigos & algoritmos que he encontrado ... No debería ser una forma más rápida para encontrar números primos, ¿usted me podría ayudar?

Answer 1

Al buscar algoritmos sobre este tema (para el proyecto Euler) no recuerdo haber encontrado algo más rápido. Si la velocidad es realmente la preocupación, ¿has pensado simplemente en almacenar los números primos, así que simplemente necesitas buscarlos?

EDITAR: búsqueda rápida de Google encontró this, confirmando que el método más rápido sería solo para buscar los resultados y buscarlos según sea necesario.

Una edición más - usted puede encontrar más información here, esencialmente un duplicado de este tema. La publicación superior allí afirma que el tamiz de Atkin fue más rápido que el de eras en cuanto a generación sobre la marcha.

Answer 2

Varios comentarios.

1. Para la velocidad, calcular previamente y luego cargar desde el disco. Es súper rápido. Lo hice en Java hace mucho tiempo.

2. No almacenar como una matriz, almacenar como una secuencia de bits para números impares. De forma más eficiente en la memoria

3. Si su pregunta de velocidad es que desea que este cálculo en particular se ejecute rápidamente (necesita justificar por qué no puede precalcular y cargarlo desde el disco) necesita codificar un mejor tamiz de Atkin. Es mas rapido. Pero solo un poco

4. No ha indicado el uso final para estos números primos. Es posible que nos perdamos algo completamente porque no nos ha dicho la aplicación. Cuéntanos un boceto de la aplicación y las respuestas se orientarán mejor para tu contexto.

5. ¿Por qué crees que algo más rápido existe? No has justificado tu corazonada. Este es un problema muy difícil. (Que es encontrar algo más rápido)

Answer 3

se puede hacer mejor que la obtenida con el Sieve of Atkin, pero es bastante difícil de poner en práctica de forma rápida y correctamente. Una simple traducción del pseudocódigo de Wikipedia probablemente no sea lo suficientemente buena.

Answer 4

El algoritmo más rápido en mi experiencia hasta ahora es el Tamiz de Erathostenes con factorización de ruedas para 2, 3 y 5, donde los números primos entre los números restantes se representan como bits en una matriz de bytes. En Java, en un núcleo de mi computadora portátil de 3 años, toma 23 segundos calcular los números primos hasta 1 mil millones.

Con la factorización de la rueda del tamiz de Atkin era aproximadamente un factor de dos más lento, mientras que con un ordinario BitSet era aproximadamente un 30% más rápido.

Véase también this answer.

Answer 5

Hice un algoritmo que puede encontrar números primos del rango 2-90 000 000 para 0.65 segundos en I 350M-notebook, escrito en C .... debe usar operaciones bit a bit y tiene "código" para recalcular el índice de su matriz al índice de bit concreto que desee. Por ejemplo, si usted quiere pliegues del número 2, trozos de hormigón serán por ejemplo .... 10101000 ... así que si usted lee de izquierda ... se obtiene el índice 4,6,8 ... eso es todo