¿Código más eficiente para los primeros 10000 números primos?

votos
49

Quiero imprimir los primeros 10000 números primos. ¿Alguien puede darme el código más eficiente para esto? Aclaraciones:

  1. No importa si tu código es ineficiente para n> 10000.
  2. El tamaño del código no importa.
  3. No puedes codificar los valores de ninguna manera.
Publicado el 03/08/2008 a las 06:45
fuente por usuario
En otros idiomas...                            


28 respuestas

votos
41

El Tamiz de Atkin es probablemente lo que estás buscando, su tiempo límite de ejecución es O (N / log log N).

Si solo ejecuta los números 1 más y 1 menos que los múltiplos de 6, podría ser aún más rápido, ya que todos los números primos por encima de 3 están a 1 de distancia de un múltiplo de seis. Recurso para mi declaración

Respondida el 03/08/2008 a las 07:03
fuente por usuario

votos
35

Recomiendo un tamiz, ya sea el Tamiz de Eratóstenes o el Tamiz de Atkin.

El tamiz o Eratóstenes es probablemente el método más intuitivo para encontrar una lista de primos. Básicamente tú:

  1. Escriba una lista de números del 2 al límite que desee, digamos 1000.
  2. Tome el primer número que no esté tachado (para la primera iteración esto es 2) y tache todos los múltiplos de ese número de la lista.
  3. Repite el paso 2 hasta llegar al final de la lista. Todos los números que no están tachados son primos.

Obviamente hay bastantes optimizaciones que se pueden hacer para que este algoritmo funcione más rápido, pero esta es la idea básica.

El tamiz de Atkin usa un enfoque similar, pero desafortunadamente no sé lo suficiente como para explicarte. Pero sí sé que el algoritmo que he vinculado toma 8 segundos para calcular todos los números primos hasta 1000000000 en un antiguo Pentium II-350

Tamiz de Eratóstenes Código Fuente: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Código fuente de Sieve of Atkin: http://cr.yp.to/primegen.html

Respondida el 06/08/2008 a las 00:49
fuente por usuario

votos
17

Esto no es estrictamente contrario a la restricción de codificación rígida, pero llega terriblemente cerca. ¿Por qué no descargar programáticamente esta lista e imprimirla?

http://primes.utm.edu/lists/small/10000.txt

Respondida el 31/08/2008 a las 23:20
fuente por usuario

votos
11

GateKiller , ¿qué le parece agregarle breaka eso ifen el foreachbucle? Eso sería acelerar las cosas mucho , porque si como 6 es divisible por 2 que no es necesario comprobar con 3 y 5. (Votaría su solución de todos modos si tuviera 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 + " ");
    }
}
Respondida el 27/08/2008 a las 21:26
fuente por usuario

votos
9

En Haskell, podemos escribir casi palabra por palabra la definición matemática de la criba de Eratóstenes, " los números primos son números naturales anteriores 1 sin ningún números compuestos, en los que se encuentran compuestos por enumeración de los múltiplos de cada primo ":

primes = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) 
                                [] primes)

primes !! 10000 es casi instantánea.

referencias:


El código anterior es ajustado fácilmente en trabajar sólo en probabilidades, primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Complejidad de tiempo es mucho mejor (a casi un registro de factor de arriba óptimo) por plegado en una estructura de árbol, y la complejidad espacio se mejoró drásticamente por la producción de números primos de múltiples etapas , 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 usan para agrupar, una llamada de función se significa simplemente por yuxtaposición, (:)es un contras operador para las listas, y (.)es un operador de composición funcional: (f . g) x = (\y-> f (g y)) x = f (g x)).

Respondida el 24/04/2012 a las 17:30
fuente por usuario

votos
9

@Matt: log (log (10000)) es ~ 2

Del artículo de wikipedia (que citó) Sieve of Atkin :

Este tamiz calcula números primos hasta N usando O(N/log log N)operaciones con solo N 1/2 + o (1) bits de memoria. Eso es un poco mejor que el tamiz de Eratóstenes que usa O(N) operaciones y O (N 1/2 (log log N) / log N) bits de memoria (AOL Atkin, DJ Bernstein, 2004) . Estas complejidades computacionales asintóticas incluyen optimizaciones simples, como la factorización de las ruedas, y la división del cálculo en bloques más pequeños.

Dadas las complejidades computacionales asintóticas a lo largo O(N)(para Eratóstenes) y O(N/log(log(N)))(para Atkin) no podemos decir (para las pequeñas N=10_000) qué algoritmo, si se implementa, será más rápido.

Achim Flammenkamp escribió en El tamiz de Eratóstenes :

citado por:

@ num1

Para intervalos mayores alrededor de 10 ^ 9, seguramente para aquellos> 10 ^ 10, el Tamiz de Eratóstenes es superado por el Tamiz de Atkins y Bernstein que usa formas cuadráticas binarias irreductibles. Consulte su documento para obtener información de antecedentes, así como el párrafo 5 del Ph.D. de W. Galway. tesis.

Por lo tanto, para 10_000Sieve of Eratosthenes puede ser más rápido que Sieve of Atkin.

Para responder a OP el código es prime_sieve.c (citado por num1)

Respondida el 06/10/2008 a las 21:03
fuente por usuario

votos
7

Usando GMP, uno podría escribir lo 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 Macbook Pro a 2.33 GHz, se ejecuta de la siguiente manera:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Cálculo de 1,000,000 primos en la misma computadora portátil:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP está altamente optimizado para este tipo de cosas. A menos que realmente desee comprender los algoritmos escribiendo el suyo, se le aconsejará usar libGMP en C.

Respondida el 29/08/2008 a las 08:06
fuente por usuario

votos
4

He adaptado el código encontrado en CodeProject para crear lo 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 + " ");
    }
}

Probar esto en mi Servidor ASP.NET tomó la rountine alrededor de 1 minuto para ejecutarse.

Respondida el 05/08/2008 a las 20:55
fuente por usuario

votos
4

No es eficiente en absoluto, pero puede usar una expresión regular para probar los números primos.

/^1?$|^(11+?)\1+$/

Esto prueba si, para una cadena que consta de k " 1" s, k no es primo (es decir, si la cadena consta de un " 1" o cualquier cantidad de " 1" s que se pueda expresar como un producto n -ary).

Respondida el 03/08/2008 a las 19:52
fuente por usuario

votos
3

Aquí hay un Tamiz de Eratóstenes que escribí en PowerShell hace unos días. Tiene un parámetro para identificar la cantidad de números primos que se deben devolver.

#
# 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
}
Respondida el 07/09/2009 a las 19:52
fuente por usuario

votos
3

Sieve of Eratosthenes es el camino a seguir, debido a su simplicidad y velocidad. Mi implementació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;
}

Tiempo de CPU para encontrar primos (en Pentium Dual Core E2140 1.6 GHz, utilizando un solo núcleo)

~ 4s por lim = 100,000,000

Respondida el 21/08/2008 a las 00:45
fuente por usuario

votos
2

El algoritmo de criba deque 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 del tamiz de Atkin, que es un ejercicio puramente académico).

La idea básica detrás del algoritmo de criba deque es utilizar un tamiz pequeño, corredera que es sólo lo suficientemente grande como para contener al menos un múltiple independiente para cada uno de los factores que actualmente 'activos' prime - es decir, los números primos cuya plaza no exceda el número más bajo Actualmente representado por el tamiz en movimiento. Otra diferencia con el estado del medio ambiente es que las tiendas de tamiz deque los factores reales en las ranuras de los materiales compuestos, no booleanos.

El algoritmo se extiende el tamaño de la ventana de tamiz según sea necesario, resultando en bastante uniforme el rendimiento de un amplio intervalo hasta que el tamiz comienza exceder la capacidad de la memoria caché L1 de la CPU de forma apreciable. El último primer que se ajuste plenamente es 25237523 (el primer 1,579,791st), lo que da una cifra aproximada aproximada para el rango de funcionamiento razonable del algoritmo.

El algoritmo es bastante simple y robusta, y tiene un rendimiento aún en un rango más amplio que una criba de Eratóstenes no segmentado. Este último es mucho más rápido, siempre y su tamiz encaja plenamente en la memoria caché, es decir, hasta 2 ^ 16 para un odds-only tamiz con Bools bytes de tamaño. Entonces su rendimiento cae cada vez más, aunque siempre sigue siendo significativamente más rápido que el deque pesar de la desventaja (por lo menos en lenguajes compilados como C / C ++, Pascal o Java / C #).

Aquí es una representación del algoritmo de criba deque en C #, porque me parece que el lenguaje - a pesar de sus muchos defectos - mucho más práctico para los algoritmos de creación de prototipos y la experimentación que el sumamente engorroso y pedante C ++. (Nota al margen: Estoy usando la libre LINQPad que permite bucear en derecho, sin todo el desorden con la creación de proyectos, archivos make, directorios o lo que sea, y me da el mismo grado de interactividad como un símbolo del pitón).

C # no tiene un tipo deque explícita, pero la llanura List<int>funciona lo suficientemente bien como para demostrar el algoritmo.

Nota: esta versión no usa un deque de los números primos, ya que simplemente no tiene sentido hacer estallar sqrt (n) de n números primos. Qué bueno sería para eliminar el 100 números primos y dejar 9900? Al menos esta manera todos los primos se recogen en un vector ordenado, 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;
    }
}

Estas son las dos funciones de ayuda:

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 tamiz segmentado especial de Eratóstenes con un tamaño de segmento 1, acompañado de un área de desbordamiento, donde los números primos vienen a descansar cuando disparan sobre el extremo del segmento. Excepto que la célula individual del segmento (alias sieve[0]) ya ha sido tamizada cuando lleguemos a él, ya que fue atropellado mientras que era parte del área de desbordamiento.

El número que está representado por sieve[0]se mantiene en sieve_base, aunque sieve_front, o window_basetambién sería una buena nombres que permiten trazar paralelismos con código de Ben o implementaciones de tamices segmentados / ventana.

Si sieve[0]contiene un valor distinto de cero, entonces ese valor es un factor de sieve_base, que de este modo puede ser reconocido como compuesto. Dado que las células 0 es un múltiplo de ese factor es fácil calcular su siguiente salto, que es simplemente 0 más ese factor. En caso de que la célula de ser ocupado ya por otro factor a continuación, sólo tenemos que añadir el factor de nuevo, y así sucesivamente hasta que nos encontramos con un múltiplo del factor donde ningún otro factor que está aparcado en la actualidad (extendiendo el tamiz si es necesario). Esto también significa que no hay necesidad de almacenar los desplazamientos de trabajo actuales de los distintos números primos de un segmento al siguiente, como en un tamiz segmentado normal. Cada vez que nos encontramos en un factor sieve[0], su actual compensada de trabajo es 0.

El primer corriente entra en el juego de la siguiente manera. Un primer solo puede ponerse al día después de su propia ocurrencia en la corriente (es decir, cuando se ha detectado como un primo, porque no marcado con un factor), y permanecerá vigente hasta que el momento exacto en que sieve[0]llega a su plaza. Todos los múltiplos bajos de este primer deben haber sido golpeado fuera debido a las actividades de los números primos más pequeños, al igual que en un estado del medio ambiente normal. Pero ninguno de los números primos más pequeños puede afectar a lado de la plaza, ya que el único factor de la plaza es el propio primer y todavía no está en circulación en este punto. Eso explica las medidas adoptadas por el algoritmo en el caso sieve_base == current_prime_squared(lo que implica sieve[0] == 0, por cierto).

Ahora el caso sieve[0] == 0 && sieve_base < current_prime_squaredes fácil de explicar: esto significa que sieve_baseno puede ser un múltiplo de cualquiera de los números primos más pequeños que el primer actual, o de lo contrario habría sido marcado como compuesto. No puedo ser un múltiplo más alto del primer actual tampoco, ya que su valor es inferior cuadrada del primer curso. Por lo tanto, debe ser un nuevo primer.

El algoritmo está obviamente inspirado en la criba de Eratóstenes, pero es igualmente obvio que es muy diferente. La criba de Eratóstenes deriva su mayor velocidad de la simplicidad de sus operaciones elementales: una sola adición índice y un almacén para cada paso de la operación es todo lo que hace por largos períodos de tiempo.

Aquí es un simple, no segmentado criba de Eratóstenes que normalmente utilizo para tamizado de números primos factor en el rango ushort, es decir, hasta 2 ^ 16. Para este post he modificado para que funcione más allá de 2 ^ 16 mediante la sustitución intdeushort

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 tamizar la primera 10.000 prepara un típico caché L1 de 32 se excederá KiByte pero la función sigue siendo muy rápido (fracción de milisegundo incluso en C #).

Si se compara este código para el tamiz deque entonces es fácil ver que las operaciones de la criba deque son mucho más complicado, y no se puede amortizar de manera efectiva sus gastos generales, ya que siempre lo hace el tramo más corto posible de cruces-off en una fila (exactamente un solo cruce inicial, después de saltarse todos los múltiplos que han sido tachados ya).

Nota: el código C # utiliza inten lugar de uintdebido a los nuevos compiladores tienen la costumbre de generación de código de calidad inferior para uint, probablemente, con el fin de empujar a la gente hacia enteros con signo ... En la versión C ++ del código anterior he utilizado unsigneda lo largo, de forma natural; el punto de referencia tenía que ser en C ++ porque quería que se basa en un tipo deque supuestamente adecuada ( std::deque<unsigned>; no hubo ninguna mejora del rendimiento de usar unsigned short). Aquí están los números para mi portátil Haswell (VC ++ 2015/64):

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: los tiempos de C # se doble bonita mucho exactamente el C ++ tiempos, que es bastante bueno para C # y la muestra que List<int>no se queda atrás, incluso si se abusa como un deque.

El código de tamiz sencilla todavía sopla el deque fuera del agua, a pesar de que ya está operando más allá de su rango de trabajo (tamaño L1 cache superado un 50%, con thrashing caché operadora) normal. La parte dominante aquí es la lectura de los números primos tamizadas, y esto no se ve afectada tanto por el problema de caché. En cualquier caso, la función se diseñó para tamizado de los factores de factores, es decir, de nivel 0 en una jerarquía de tamiz 3-nivel, y por lo general tiene que devolver sólo unos pocos cientos de factores o un número bajo de miles. De ahí su sencillez.

Rendimiento podría ser mejorado en más de un orden de magnitud mediante el uso de un tamiz segmentado y optimizar el código para la extracción de los números primos tamizadas (paso mod 3 y desenrolló dos veces, o mod 15 y desenrolló una vez), y aún más el rendimiento podría ser exprimido fuera de el código mediante el uso de un mod 16 o mod 30 rueda con todos los adornos (es decir desenrollado completo para todos los residuos). Algo así como que se explica en mi respuesta a Encontrar número primo posicionado primer sobre de revisión de código, donde se discutió un problema similar. Pero es difícil ver el punto en la mejora de los tiempos de sub-milisegundos para una tarea de una sola vez ...

Para poner las cosas un poco en perspectiva, aquí están los tiempos de la C ++ para el tamizado de hasta 100 millones:

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, un tamiz segmentado en C # con algunas campanas y silbatos hace el mismo trabajo en 95 ms (no C ++ horarios disponibles, ya que hago código desafía sólo en C # en el momento).

Las cosas pueden parecer decididamente diferente en un lenguaje interpretado como Python en el que cada operación tiene un alto costo y los gastos generales intérprete empequeñece todas las diferencias debidas a predicho vs ramas mispredicted o sub-ops (ciclo de cambio, adición) vs. operaciones multi-ciclo (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 la solución deque un poco más atractivo.

Además, muchos de los intervalos reportados por otros participantes en este tema probablemente están dominados por el tiempo de salida . Eso es una guerra completamente diferente, donde mi arma principal 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;
        }
    }
}

Para eso se necesita menos de 1 ms para la escritura de los números 10000 (clasificados). Es una clase estática, porque está destinado para su inclusión en la codificación textual presentaciones de desafío, con un mínimo de esfuerzo y ninguna perdida.

En general me pareció que era mucho más rápido si el trabajo se centró se realiza en lotes completos, es decir, el tamiz de un cierto rango, a continuación, extraer todos los números primos en un vector / matriz, luego la explosión a cabo toda la gama, a continuación, se tamiza la siguiente rango y así sucesivamente, en lugar de mezclar todo junto. Que tienen funciones separadas se centraron 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.

Respondida el 19/04/2016 a las 14:07
fuente por usuario

votos
2

en Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Respondida el 22/02/2010 a las 08:45
fuente por usuario

votos
2

El tamiz parece ser la respuesta incorrecta. El tamiz te da los números primos hasta un número N , no los primeros N primos. Ejecute @Imran o @Andrew Szeto, y obtendrá los números primos hasta N.

El tamiz podría ser útil si sigues probando tamices para números cada vez más grandes hasta que alcances un determinado tamaño de tu conjunto de resultados, y utilizas un poco de almacenamiento en caché de los números ya obtenidos, pero creo que todavía no sería más rápido que una solución como @ Pat's .

Respondida el 19/06/2009 a las 19:12
fuente por usuario

votos
2

Adaptando y siguiendo de GateKiller , aquí está la versión final que he usado.

    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 lo mismo, pero agregué la sugerencia "break on Sqrt" y cambié algunas de las variables para que me quedara mejor. (Estaba trabajando en Euler y necesitaba el primo 10001)

Respondida el 16/02/2009 a las 06:17
fuente por usuario

votos
1

El uso de criba de Eratóstenes, el cálculo es bastante más rápido en comparación con algoritmo de números primos "de todo el conocido".

Mediante el uso de pseudocódigo es wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), que sea 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) se lleva a 2s y 330ms.

NOTA : Valor puede variar depende de las especificaciones de hardware.

Respondida el 12/05/2016 a las 00:40
fuente por usuario

votos
1

Aquí es una solución de C ++, utilizando una forma 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 del tamiz puede calcular números primos indefinidamente.

También tenga en cuenta, el TEL dequetoma O(1)el tiempo para llevar a cabo push_back, pop_fronty de acceso aleatorio, aunque subíndices.

La resizeoperación toma O(n)tiempo, donde nse añade el número de elementos. Debido a la forma en que estamos utilizando esta función, podemos tratar esto es una constante pequeña.

El cuerpo de la whileen bucle my_insertse ejecuta O(log log n)veces, donde nes igual a la variable maybe_prime. Esto se debe a la expresión de la condición whilese evaluará como true una vez para cada factor primo maybe_prime. Consulte " función divisor " en la Wikipedia.

Multiplicando por el número de veces que my_insertse llama, muestra que tome O(n log log n)tiempo para enumerar nlos números primos ... que es, como era de esperar, la complejidad de tiempo que se supone que la criba de Eratóstenes a tener.

Sin embargo, mientras que este código es eficiente, no es el más eficiente ... Me gustaría sugerir fuertemente utilizando una biblioteca especializada para la generación de números primos, como primesieve . Cualquier solución realmente eficaz, bien optimizado, tendrá más código que alguien quiere escribir en Stackoverflow.

Respondida el 16/04/2016 a las 15:33
fuente por usuario

votos
1

El siguiente código de Mathcad calcula el primer millón de números primos en menos de 3 minutos.

Tenga en cuenta que esto sería utilizar coma flotante duplica para todos los números y es básicamente interpretado. Espero que la sintaxis es clara.

introducir descripción de la imagen aquí

Respondida el 02/03/2014 a las 02:15
fuente por usuario

votos
1

Aquí está mi código VB 2008, que busca todos los números primos <10.000.000 en 1 min 27 seg en mi portátil de trabajo. Se salta números pares y sólo busca primos que son <la raíz cuadrada del número de pruebas. Sólo está diseñado para encontrar números primos de 0 a un valor centinela.

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
Respondida el 11/03/2011 a las 03:25
fuente por usuario

votos
0

Puesto que usted quiere primeros números primos 10000 única, en lugar de codificación de algoritmo complejo voy a sugerir la 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 es primordial que lo necesite

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Respondida el 16/11/2018 a las 05:34
fuente por usuario

votos
0

Te puedo dar algunos consejos, hay que ponerla en práctica.

  1. Para cada número, obtener la mitad de ese número. Por ejemplo, para la comprobación 21, solamente obtener el resto dividiéndolo de la gama de 2-10.
  2. Si es un número impar, sólo se divide por el número impar, y viceversa. Tal como para 21, dividir con 3, 5, 7, 9 solamente.

método más eficiente llegué hasta tan lejos.

Respondida el 29/07/2018 a las 19:25
fuente por usuario

votos
0

Utilizando el método Array.prototype.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
Respondida el 09/06/2018 a las 21:49
fuente por usuario

votos
0

Aquí el código que hice:


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;
}
Respondida el 20/01/2018 a las 12:50
fuente por usuario

votos
0

Aquí está mi código que encuentra primeras 10.000 números primos en 0.049655 segundos en mi portátil, 1.000.000 primeros números primos en menos de 6 segundos y el primer 2.000.000 en 15 segundos
una pequeña explicación. Este método utiliza 2 técnicas para encontrar números primos

  1. en primer lugar cualquier número no prime es un compuesto de múltiplos de números primos lo que esta prueba código dividiendo el número de prueba por números primos más pequeños en lugar de cualquier número, esto disminuye cálculo por menos 10 veces para un número de 4 dígitos y más aún para un número más grande
  2. En segundo lugar, además de dividir por el primer, sólo se divide por números primos que son más pequeños o igual a la raíz de la cantidad que se está probando reduciendo aún más los cálculos en gran medida, esto funciona ya que cualquier número que es mayor que la raíz del número tendrá un número de contraparte que tiene que ser menor que la raíz del número, pero ya que hemos probado todos los números menores que la raíz ya, por lo tanto no necesitamos que molestarse con número mayor que la raíz del número que se está probando.

Salida de ejemplo para el primer número primo 10.000
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Aquí está el código en lenguaje C, Introduzca 1 y 10.000 para imprimir los primeros 10.000 números primos.
Editar: Olvidé este contiene biblioteca matemática, si usted está en ventanas o Visual Studio que debe estar bien, pero en Linux se debe compilar el código usando el argumento -lm o el código no puede trabajar
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);
}
Respondida el 06/05/2017 a las 08:48
fuente por usuario

votos
0

He estado trabajando en números primos encontrar para 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 al 2147483629 a partir de las 2.

Respondida el 13/08/2016 a las 21:20
fuente por usuario

votos
0

Me paso algún tiempo escribiendo un programa de cálculo de una gran cantidad de números primos y este es el código que estoy acostumbrado a calcular un archivo de texto que contiene los primeros números primos 1.000.000.000. Está en alemán, pero la parte interesante es el método calcPrimes(). Los números primos se almacenan en una matriz llamada Primzahlen. Recomiendo una CPU de 64 bits debido a que los cálculos son números enteros de 64 bits con.

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);
        }
    }
}
Respondida el 23/04/2012 a las 20:46
fuente por usuario

votos
0

He escrito este usando pitón, como acabo de empezar a aprenderlo, y funciona perfectamente bien. El primer número 10.000 generar por este código como lo mismo como se menciona en http://primes.utm.edu/lists/small/10000.txt . Para comprobar si nes primo o no, se divide npor el número de 2a sqrt(n). Si alguna de esta gama de serie perfectamente divide nentonces no es primordial.

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))
Respondida el 27/12/2010 a las 18:37
fuente por usuario

votos
-1
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();
        }
    }
}
Respondida el 08/05/2012 a las 05:15
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more