Código más eficiente para el primer 10000 números primos?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Quiero imprimir la primera 10000 números primos.Puede alguien darme el código más eficiente para esto?Aclaraciones:
- No importa si su código es ineficiente para n >10000.
- El tamaño del código, no importa.
- Usted simplemente no puede codificar los valores de cualquier manera.
Solución
El Tamiz de Atkin es probablemente lo que usted está buscando, su límite superior tiempo de ejecución es O(N/log log N).
Si sólo se ejecuta en los números 1 y 1 menor de los múltiplos de 6, podría ser incluso más rápido, como todos los números primos por encima de 3 1, lejos de algún múltiplo de seis.Recursos para mi declaración
Otros consejos
Recomiendo un colador, el Criba de Eratóstenes o el Tamiz de Atkin.
El cedazo o Eratóstenes es probablemente el más intuitivo método de búsqueda de una lista de números primos.Básicamente, usted:
- Escriba una lista de números de 2 a cualquier límite desea, digamos 1000.
- Tomar el primer número que no está tachada (para la primera iteración esta es la 2) y entre todos los múltiplos de ese número de la lista.
- Repita el paso 2 hasta que llegue al final de la lista.Todos los números que no están tachados son los principales.
Obviamente hay bastante un par de optimizaciones que se pueden hacer para hacer de este algoritmo trabaja más rápido, pero esta es la idea básica.
El tamiz de Atkin utiliza un enfoque similar, pero por desgracia no sé lo suficiente sobre él para que se lo explique.Pero sí sé que el algoritmo he enlazado tarda 8 segundos para averiguar todos los números primos hasta 1000000000 en un antiguo Pentium II a 350
Criba de Eratóstenes Código Fuente: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Tamiz de Atkin Código Fuente: http://cr.yp.to/primegen.html
Esto no es totalmente en contra de la codificar restricción, pero viene terriblemente cerca.¿Por qué no a través de programación de descarga de esta lista y a imprimir, en lugar?
GateKiller, ¿cómo sobre la adición de un break para que if en el foreach bucle?Que podría acelerar las cosas mucho porque si como 6 es divisible por 2 no es necesario comprobar con 3 y 5.(Yo iba a votar a su solución, de todos modos si yo tenía la reputación suficiente :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
En Haskell, podemos escribir casi palabra por palabra a la definición matemática de la criba de Eratóstenes "los números primos son números naturales de más de 1 sin cualquier compuesto de números, donde son encontrados por la enumeración de cada uno de los prime múltiplos":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 es casi instantáneo.
Referencias:
El código anterior es fácilmente ajustado a trabajar en las probabilidades sólo, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).El tiempo de complejidad es mucho mejor (a sólo una registro de factor encima de lo óptimo) mediante el plegado en una estructura de árbol, y el espacio de la complejidad mejorado drásticamente por multietapa de los números primos de la producción, en
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(En Haskell los paréntesis se utilizan para agrupar, una llamada a una función se expresa sólo por la yuxtaposición, (:) es un contras operador para las listas, y (.) es una composición funcional del operador: (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt:log(log(10000)) es de ~2
Desde el artículo de la wikipedia (que se citan) Tamiz de Atkin:
Este tamiz calcula los números primos hasta N el uso de
O(N/log log N)operaciones con sólo N1/2+o(1) bits de memoria.Que es un poco mejor que el tamiz de Eratóstenes que utilizaO(N)operaciones y O(N1/2(log log N)/log N) bits de memoria (A. O. L.Atkin, D. J.Bernstein, 2004).Estos asintótica computacional complejidades incluyen simple optimizaciones, tales como la rueda factorización, y la división de la cálculo bloques más pequeños.
Dado asintótica computacional complejidad a lo largo de O(N) (por Eratóstenes) y O(N/log(log(N))) (por Atkin) no podemos decir (para los pequeños N=10_000) el algoritmo que, si se implementan será más rápido.
Achim Flammenkamp escribió en La Criba de Eratóstenes:
citado por:
@num1
Para los intervalos más grandes alrededor de 10^9, seguramente para aquellos > 10^10, el Tamiz de Eratóstenes es superado por el Tamiz de Atkins y Bernstein que utiliza irreductible cuadráticas binarias los formularios.Ver a su papel de fondo informaciones así como el párrafo 5 de la W.Galway del D. Tel.tesis.
Por lo tanto para 10_000 Criba de Eratóstenes puede ser más rápido, a continuación, Tamiz de Atkin.
Para responder OP el código es prime_sieve.c (citado por num1)
El uso de GMP, podría escribir la siguiente:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
En mi 2.33 GHz Macbook Pro, se ejecuta de la siguiente manera:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
El cálculo de 1.000.000 de números primos en el mismo ordenador portátil:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP es altamente optimizado para este tipo de cosas.A menos que usted realmente desea entender los algoritmos de escribir su propio, usted sería aconseja el uso de libgmp, ya que bajo C.
No es eficaz en absoluto, pero puede utilizar una expresión regular para la prueba de los números primos.
/^1?$|^(11+?)\1+$/
Este análisis si, por una cadena que consta de k “1"s, k es no prime (es decir,si la cadena se compone de uno "1"o cualquier número de "1"s que puede ser expresado como un n-ary producto).
He adaptado código que se encuentra en la CodeProject para crear el siguiente:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
La prueba esta en mi ASP.NET Servidor tuvo la rountine alrededor de 1 minuto para que se ejecute.
Aquí es una Criba de Eratóstenes que escribí en PowerShell hace un par de días.Tiene un parámetro para identificar el número de números primos que debe ser devuelto.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
Criba de Eratóstenes es el camino a seguir, debido a su sencillez y velocidad.Mi aplicación en C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
El Tiempo de la CPU para encontrar los números primos (en Pentium Dual Core E2140 1.6 GHz, usando un solo núcleo)
~ 4s para lim = 100.000.000 de
La adaptación y después de GateKiller, aquí está la versión final que yo he utilizado.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
Es básicamente el mismo, pero he añadido el "break on Sqrt" sugerencia y cambiado algunas de las variables alrededor para que se ajuste mejor para mí.(Yo estaba trabajando en Euler y necesitaba el 10001th prime)
El Tamiz parece ser la respuesta equivocada.El tamiz le da los números primos hasta un número N, no la el primer N los números primos.Ejecutar @Imran o @Andrew Szeto, y obtener los números primos hasta N.
El tamiz todavía podría ser útil si sigues tratando de tamices para cada vez un mayor número hasta llegar a un cierto tamaño de su conjunto de resultados, y el uso de algunas de almacenamiento en caché de los números ya se ha obtenido, pero creo que aún sería no más que una solución como @Pat.
En Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
El deque tamiz algoritmo mencionado por BenGoldberg merece un vistazo más de cerca, no sólo porque es muy elegante, pero también porque en ocasiones puede ser útil en la práctica (a diferencia de la Criba de Atkin, que es puramente académica ejercicio).
La idea básica detrás de la deque tamiz algoritmo es el uso de un pequeño deslizamiento tamiz que es sólo lo suficientemente grande como para contener al menos una por separado múltiples para cada uno de los actualmente activas factores primos - es decir,los números primos cuyo cuadrado no supera el número más bajo en la actualidad representada por el movimiento del tamiz.Otra diferencia con el SoE es que el deque tamiz de las tiendas de los factores reales en las ranuras de los composites, no booleanos.
El algoritmo se extiende el tamaño de la criba ventana como la que se necesita, lo que resulta en bastante incluso el rendimiento en un amplio rango de hasta el tamiz empieza a exceder la capacidad de la CPU caché L1 de forma apreciable.El último prime que se ajusta plenamente es 25,237,523 (el 1,579,791 st prime), que da un duro cifra aproximada razonable por el rango de funcionamiento del algoritmo.
El algoritmo es bastante simple y robusto, y tiene incluso su rendimiento a través de una gama mucho más amplia de una segmentado Criba de Eratóstenes.El último es mucho más rápido de su tamiz encaja completamente en la memoria caché, es decir,hasta 2^16 para un odds-sólo tamiz de tamaño en bytes bools.A continuación, su rendimiento cae más y más, aunque siempre sigue siendo significativamente más rápido que el deque a pesar de la desventaja (al menos en los lenguajes compilados como C/C++, Pascal o Java/C#).
Aquí es una representación de la deque tamiz algoritmo en C#, porque me parece que el lenguaje - a pesar de sus muchos defectos, mucho más práctico para la creación de prototipos de los algoritmos y la experimentación de la sumamente engorroso y pedante C++. (Nota al margen:Estoy usando la libre LINQPad lo que hace posible la inmersión en el derecho, sin todo el alboroto con la configuración de proyectos, makefiles, directorios o lo que sea, y me da el mismo grado de interactividad como una de python del sistema).
C# no de forma explícita deque tipo, pero la llanura List<int> funciona lo suficientemente bien como para demostrar que el algoritmo.
Nota:esta versión no utiliza un deque para los números primos, porque simplemente no tiene sentido para hacer estallar sqrt(n) de n números primos.Qué bueno sería para eliminar 100 de los números primos y dejar 9900?Al menos de esta manera todos los números primos son recogidos en una casa de vectores, listo para su posterior procesamiento.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
Aquí están las dos funciones auxiliares:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
Probablemente la forma más fácil de entender el algoritmo es imaginarlo como un especial segmentada Criba de Eratóstenes con un tamaño de segmento 1, acompañado por un desbordamiento de la zona donde los números primos vienen a descansar cuando se dispara sobre el final del segmento.Excepto que la única célula del segmento (un.k.una. sieve[0]) ya ha sido tamizada cuando se llega a él, porque fue atropellado mientras era parte del área de desbordamiento.
El número que está representado por sieve[0] se celebra en sieve_base, aunque sieve_front o window_base también sería una buena nombres que permiten trazar paralelismos a Ben del código o de las implementaciones de segmentados/de ventana de tamices.
Si sieve[0] contiene un valor distinto de cero, entonces, que el valor es un factor de sieve_base, que por lo tanto puede ser reconocido como compuesto.Desde la celda 0 es un múltiplo de ese factor es fácil calcular su siguiente salto, que es simplemente 0 más de ese factor.En caso de que la celda ser ocupado ya por otro factor, a continuación, sólo tenemos que añadir el factor de nuevo, y así sucesivamente hasta encontrar un múltiplo de que el factor de que ningún otro factor es actualmente estacionado (ampliando el tamiz si es necesario).Esto también significa que no hay necesidad de almacenar la corriente de trabajo de desplazamientos de los varios primos de un segmento a otro, como en una normal segmentado tamiz.Cada vez que nos encontramos con un factor en sieve[0], su trabajo actual offset es 0.
El actual primer entra en juego en la forma siguiente.Un primer sólo puede hacerse después de que su propia aparición en la secuencia (es decir,cuando se ha detectado como una de las principales, porque no se marcan con un factor), y permanecerá vigente hasta el momento exacto en el que sieve[0] llega a su plaza.Todo menor de los múltiplos de este primer debe haber sido golpeado debido a las actividades de los más pequeños de los números primos, como en una normal de SoE.Pero ninguno de los que el más pequeño de los números primos pueden huelga fuera de la plaza, ya que el único factor de la plaza es el prime y que todavía no está en circulación en este punto.Que explica las medidas tomadas por el algoritmo en el caso sieve_base == current_prime_squared (lo que implica sieve[0] == 0, que , por cierto).
Ahora el caso sieve[0] == 0 && sieve_base < current_prime_squared es fácil de explicar:esto significa que sieve_base no puede ser un múltiplo de cualquiera de los números primos más pequeños que el actual primer, o de lo contrario habría sido marcados como compuesto.No puedo ser un mayor múltiplo de la corriente de prime, ya que su valor es menor que el actual primer plaza.Por lo tanto debe ser un nuevo prime.
El algoritmo es, obviamente inspirado por la Criba de Eratóstenes, pero igualmente claro que es muy diferente.La Criba de Eratóstenes se deriva de su superior velocidad de la simplicidad de su elementales operaciones:un único índice de la suma y una tienda para cada paso de la operación es todo lo que hace por largos períodos de tiempo.
Aquí es un simple, sin segmentar Criba de Eratóstenes que yo uso normalmente para el cribado de factor de los números primos en la ushort rango, es decir,hasta 2^16.Para este post he modificado para trabajar más allá de 2^16 sustituyendo int para ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
Cuando cribado en el primer 10000 prepara un típico caché L1 de 32 KiByte será superado, pero la función es todavía muy rápido (fracción de un milisegundo incluso en C#).
Si se compara este código para el deque tamiz entonces es fácil ver que las operaciones de la deque tamiz son mucho más complicada, y que efectivamente no se pueden amortizar sus gastos, ya que siempre el menor posible tramo de cruces en una fila (exactamente un único cruce-off, después de saltar todos los múltiplos que se han cruzado ya).
Nota:el código de C# usa int en lugar de uint ya que las nuevas versiones de los compiladores tienen un hábito de la deficiente generación de código para uint, probablemente con el fin de empujar a las personas hacia enteros...En la versión de C++ de código que he usado unsigned todo, naturalmente;el punto de referencia tenía que ser en C++ porque quería que se basa en un supuesto adecuado deque tipo (std::deque<unsigned>;no hubo aumento en el rendimiento del uso de unsigned short).Aquí están los números de mi Haswell portátil (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Nota:el C# veces son casi exactamente el doble de la de C++ tiempos, lo cual es bastante bueno para C# y ìt muestra que List<int> no se queda atrás, incluso si se abusa como deque.
El simple tamiz código todavía sopla el deque fuera del agua, aunque ya está funcionando más allá de su rango de trabajo normal (L1 tamaño de la caché supera en un 50%, con los consiguientes caché de la trilla).El domina parte aquí es la lectura de la criba de los números primos, y esto no es muy afectado por el problema de caché.En cualquier caso, la función se ha diseñado para el cribado de los factores de factores, es decir,nivel 0 en un 3-nivel tamiz de la jerarquía, y por lo general tiene que devolver sólo un par de cientos de factores o a un número bajo de miles de personas.De ahí su sencillez.
El rendimiento puede ser mejorado por más de un orden de magnitud por el uso de la segmentación del tamiz y la optimización del código para extraer el tamizado de los números primos (caminado mod 3 y desplegó dos veces, o mod 15 y desenrolla una vez) , y aún más el rendimiento podría ser expulsados del código mediante el uso de un mod 16 o mod 30 de la rueda con todas las de la ley (es decir,total de desenrollar para todos los residuos).Algo así como que se explica en mi respuesta a Encontrar el primer posicionado en el primer número sobre la Revisión del Código, donde un problema similar se discuten.Pero es difícil ver el punto en el mejoramiento de la sub-milisegundos veces para una tarea...
Para poner las cosas un poco en perspectiva, aquí están los de C++ tiempos para el cribado de hasta 100.000.000 de:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
Por el contrario, la segmentación del tamiz en C# con un par de campanas y silbatos hace el mismo trabajo en el 95 ms (no C++ tiempos disponibles, ya que el código de desafíos sólo en C# en el momento).
Las cosas pueden parecer muy diferente en lenguajes interpretados como Python, donde cada operación tiene un coste enorme y el intérprete de la sobrecarga de enanos todas las diferencias debido a la predijo vsmispredicted ramas o sub-ciclo de operaciones (cambio, adición) vsmulti-ciclo de operaciones (multiplicación, y tal vez incluso la división).Que está obligado a erosionar la ventaja de la simplicidad de la Criba de Eratóstenes, y esto podría hacer que las deque solución un poco más atractivo.
También, muchos de los intervalos reportados por otros encuestados en este tema son, probablemente, dominado por tiempo de salida de la.Eso es completamente distinta a la de la guerra, donde mi principal arma es una clase simple como esto:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
Que tarda menos de 1 ms para escribir 10000 (ordenadas) de los números.Es una clase estática, porque está destinado textual inclusión en la codificación desafío de las presentaciones, con un mínimo de alboroto y cero gastos generales.
En general me pareció que para ser mucho más rápido si se centra el trabajo se realiza en lotes enteros, lo que significa tamiz de un cierto rango, a continuación, extraer todos los números primos en un vector o matriz, entonces la explosión de la totalidad de la matriz, a continuación, tamiz de la siguiente rango, y así sucesivamente, en lugar de mezcla todo junto.Tener separadas las funciones centrado en tareas específicas también hace que sea más fácil de mezclar y combinar, que permite la reutilización, y facilita el desarrollo/pruebas.
Aquí está mi VB 2008 código, el cual busca todos los números primos <10,000,000 en 1 minuto 27 segundos en mi portátil.Se salta un número par y sólo busca los números primos que son < la raíz cuadrada del número de la prueba.Que sólo está diseñado para encontrar los números primos desde 0 a un sentinel valor.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
El siguiente Mathcad código calcula el primer millón de números primos en menos de 3 minutos.
Tenga en cuenta que este sería el uso de punto flotante dobles para todos los números y básicamente es interpretado.Espero que la sintaxis es clara.
Aquí es un C++, usando un formulario de SoE:
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
Tenga en cuenta que esta versión de el Tamiz puede calcular números primos de forma indefinida.
Tenga en cuenta también, la STL deque toma O(1) tiempo para realizar push_back, pop_front, y de acceso aleatorio a pesar de suscripción.
El resize la operación se lleva a O(n) el tiempo, donde n es el número de elementos añadidos.Debido a cómo estamos utilizando esta función, se puede tratar esta es una pequeña constante.
El cuerpo de la while bucle en my_insert se ejecuta O(log log n) tiempos, en donde n es igual a la variable maybe_prime.Esto es debido a que la expresión de condición de la while se evalúan a cierto una vez para cada factor primo de maybe_prime.Ver "Divisor de la función"en la Wikipedia.
Multiplicando por el número de veces que my_insert se llama, muestra que se debe tomar O(n log log n) tiempo a lista n los números primos...que es, como era de esperar, el tiempo, la complejidad en la que la Criba de Eratóstenes se supone que tiene.
Sin embargo, mientras que este código es eficiente, no es el más eficiente...Me atrevería a sugerir el uso de una biblioteca especializada para los primos de generación, tales como primesieve.Cualquier verdaderamente eficientes, bien optimizado solución, va a tomar más de lo que nadie quiere escribir en Stackoverflow.
El uso de Criba de Eratóstenes, el cálculo es bastante más rápido en comparación con "conocido" de los números primos algoritmo.
Mediante el uso de pseudocódigo los de la wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), Voy a ser capaz de tener la solución en C#.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) tarda 2s y 330ms.
NOTA:El valor puede variar dependiendo de las Especificaciones de Hardware.
Paso algo de tiempo a escribir un programa de cálculo de un montón de primos y este es el código que estoy acostumbrado a calcular un archivo de texto que contiene la primera 1.000.000.000 de los números primos.Está en alemán, pero la parte interesante es el método calcPrimes().Los números primos son almacenados en una matriz llamada Primzahlen.Me recomienda una CPU de 64 bits, porque los cálculos con enteros de 64 bits.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
He escrito este usando python, como acabo de empezar a aprender, y funciona perfectamente bien.Los 10.000 th primer generar por este código, el mismo que se menciona en http://primes.utm.edu/lists/small/10000.txt.Para comprobar si n es primo o no, dividir n por los números de 2 a sqrt(n).Si alguno de este rango de número de la perfección divide n entonces no es primo.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
He estado trabajando en encontrar los números primos por alrededor de un año.Esto es lo que he encontrado para ser el más rápido:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 nano segundos para llegar a 2147483629 partir de los 2.
Aquí está mi código que se encuentra
primeros 10.000 números primos en 0.049655 sec en mi portátil, la primera de 1.000.000 de números primos en menos de 6 segundos y la primera de 2.000.000 en 15 segundos
Un poco de explicación.Este método utiliza 2 técnicas para encontrar un número primo
- primero de todo, cualquier no-el primer número es un compuesto de múltiplos de números primos por lo que este código de prueba dividiendo el número de la prueba por parte de pequeños números primos en lugar de cualquier número, esto disminuye el cálculo por al menos 10 veces para un número de 4 dígitos y más aún para un mayor número de
- en segundo lugar, además de dividir por el primer, sólo se divide por los números primos que son menores o iguales a la raíz de la cantidad que está siendo probado reducir aún más los cálculos en gran medida, esto funciona porque cualquier número que es mayor que la raíz de la serie tendrá una contraparte número que tiene que ser menor que la raíz de la serie, pero ya hemos probado todos los números menores que la raíz ya, por lo que no tiene que molestarse con número mayor que la raíz de la cantidad que está siendo probado.
Ejemplo de salida para los primeros 10.000 primer número
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Aquí está el código en lenguaje C,
Escriba 1 y, a continuación, de 10.000 a imprimir los primeros 10.000 números primos.
Editar:Se me olvidó este contiene la librería math ,si estás en windows o visual studio que debe estar bien, pero en linux debe compilar el código con -lm argumento o el código no funcione
Ejemplo:gcc-Wall-o "%e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
Aquí el código que he hecho :
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
Utilizando la Matriz.el prototipo.método find() en Javascript.2214.486 ms
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
Te puedo dar algunos consejos, usted tiene que implementar.
- Para cada número, obtener la mitad de ese número.E. g.para la comprobación de 21 de sólo obtener el resto a través de su división de rango 2-10.
- Si es un número impar, sólo se dividen por el número impar, y viceversa.Como para el 21 de dividir por 3, 5, 7, 9 solamente.
El método más eficaz que tengo hasta el momento.
Puesto que usted desea primer 10000 números primos sólo, en lugar de codificar algoritmo complejo que voy a sugerir el siguiente
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
ahora llamada prime como usted lo necesita
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
