La forma más elegante de generar números primos [cerrado]

84

Cuál es la forma más elegante de implementar esta función:

ArrayList generatePrimes(int n)

Esta función genera los primeros nnúmeros primos (editar: donde n>1), por generatePrimes(5)lo que devolverá un ArrayListcon {2, 3, 5, 7, 11}. (Estoy haciendo esto en C #, pero estoy contento con una implementación de Java, o cualquier otro lenguaje similar para el caso (así que no Haskell)).

Sé cómo escribir esta función, pero cuando lo hice anoche no terminó tan bien como esperaba. Esto es lo que se me ocurrió:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

No me preocupa demasiado la velocidad, aunque no quiero que sea obviamente ineficiente. No me importa qué método se use (ingenuo o tamiz o cualquier otra cosa), pero quiero que sea bastante breve y obvio cómo funciona.

Editar : Gracias a todos los que han respondido, aunque muchos no respondieron mi pregunta real. Para reiterar, quería un buen código limpio que generara una lista de números primos. Ya sé cómo hacerlo de diferentes maneras, pero soy propenso a escribir código que no es tan claro como podría ser. En este hilo se han propuesto algunas buenas opciones:

  • Una versión más bonita de lo que tenía originalmente (Peter Smit, jmservera y Rekreativc)
  • Una implementación muy limpia del tamiz de Eratosthenes (starblue)
  • Use Java's BigIntegersy nextProbablePrimepara un código muy simple, aunque no puedo imaginar que sea particularmente eficiente (dfa)
  • Utilice LINQ para generar perezosamente la lista de números primos (Maghis)
  • Coloque muchos números primos en un archivo de texto y léalos cuando sea necesario (darin)

Edición 2 : implementé en C # un par de los métodos que se dan aquí y otro método que no se menciona aquí. Todos encuentran los primeros n números primos de manera efectiva (y tengo un método decente para encontrar el límite para proporcionar a los tamices).

David Johnstone
fuente
12
no, y tampoco es para Project Euler :-)
David Johnstone
1
Sería mejor para mí devolver ienumerable <int> y ceder uno por uno
Felice Pollano
4
Lo que me gustaría saber es cuál es la forma menos elegante de generar números primos. ¿Estoy pensando en algo relacionado con una base de datos de Access?
j_random_hacker
1
para la comparación, un código de Haskell 2008 por BMeph : nubBy (((>1).).gcd) [2..]. Deja solo no duplicados entre los números naturales, comenzando desde 2, considerando como duplicado cualquier número cuyo gcdcon cualquiera de los números encontrados anteriormente sea mayor que 1. Es muy ineficiente, cuadrático en el número de primos producidos. Pero es elegante .
Will Ness
el más elegante , en mi opinión, es el de Haskell, import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) }pero eso, por supuesto , se basa totalmente en opiniones .
Will Ness

Respuestas:

48

Usa la estimación

pi(n) = n / log(n)

para el número de primos hasta n para encontrar un límite, y luego use un tamiz. La estimación subestima un poco el número de números primos hasta n, por lo que el tamiz será un poco más grande de lo necesario, lo cual está bien.

Este es mi tamiz Java estándar, calcula el primer millón de números primos en aproximadamente un segundo en una computadora portátil normal:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}
estrella azul
fuente
3
Esa es una muy buena implementación del tamiz de Eratosthenes
David Johnstone
1
¿No sería suficiente hacer un bucle i <= Math.sqrt(limit)en el bucle exterior?
Christoph
1
@David Johnstone No, pi (n) = n / log (n) subestima el número de primos hasta n, que va en la dirección opuesta. Sin embargo, me alegra que hayas encontrado una aproximación mucho más agradable.
starblue
1
si está dispuesto a eliminar todos los múltiplos de 2 en su propio bucle, puede usar j + = 2 * i como su incremento de bucle para ahorrar algo de tiempo de ejecución adicional, y puede calcularlo una vez usando un cambio de bit
Nick Larsen
5
Al reemplazarlo BitSetpor una clase que implementa la factorización de rueda para 2, 3 y 5, se vuelve casi 3 veces más rápido.
starblue
37

Muchas gracias a todos los que dieron respuestas útiles. Aquí están mis implementaciones de algunos métodos diferentes para encontrar los primeros n números primos en C #. Los dos primeros métodos son prácticamente los que se publicaron aquí. (Los nombres de los carteles están al lado del título). Planeo hacer el tamiz de Atkin en algún momento, aunque sospecho que no será tan simple como los métodos aquí actualmente. Si alguien puede ver alguna forma de mejorar alguno de estos métodos, me encantaría saberlo :-)

Método estándar ( Peter Smit , jmservera , Rekreativc )

El primer número primo es 2. Agregue esto a una lista de primos. El siguiente primo es el siguiente número que no es divisible de manera uniforme por ningún número de esta lista.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

Esto se ha optimizado probando solo la divisibilidad hasta la raíz cuadrada del número que se está probando; y solo probando números impares. Esto se puede optimizar aún más probando solo números del formulario 6k+[1, 5], 30k+[1, 7, 11, 13, 17, 19, 23, 29]o así sucesivamente .

Tamiz de Eratóstenes ( azul estrella )

Esto encuentra todos los números primos de k . Para hacer una lista de los primeros n primos, primero necesitamos aproximar el valor del n- ésimo primo. El siguiente método, como se describe aquí , hace esto.

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

Tamiz de Sundaram

Recientemente descubrí este tamiz , pero se puede implementar de manera bastante simple. Mi implementación no es tan rápida como el tamiz de Eratóstenes, pero es significativamente más rápida que el método ingenuo.

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}
David Johnstone
fuente
FYI - Tuve que cambiar su contador de bucle principal a "for (int i = 0; i * i <= limit && i * i> 0; i ++)" para evitar un desbordamiento.
Jacobs Data Solutions
Esta implementación del Tamiz de Sundaram es una de las pocas correctas que existen. La mayoría de ellos usan límites incorrectos para i y j mientras calculan i+j+2*i*jlo que conduce a una salida incorrecta.
jahackbeth
15

Resolviendo una vieja pregunta, pero me tropecé con ella mientras jugaba con LINQ.

Este código requiere .NET4.0 o .NET3.5 con extensiones paralelas

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}
spookycoder
fuente
1
¿Por qué no es esta la respuesta aceptada? El código aquí es mucho más corto, más elegante y mucho más rápido que el código de la respuesta aceptada. ¡Ojalá pudiera votar a favor más de una vez!
Avrohom Yisroel
9

Estás en el buen camino.

Algunos comentarios

  • primos.Añadir (3); hace que esta función no funcione para número = 1

  • No tiene que probar la división con números primos más grandes que la raíz cuadrada del número que se va a probar.

Código sugerido:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}
Peter Smit
fuente
1
probar que prime * prime <= curTest en el ciclo en lugar de precalcular la raíz cuadrada probablemente lo hará más rápido y lo hará más genérico (funcionará para bignums, etc.)
yairchu
¿Por qué usar la raíz cuadrada? ¿Cuál es el trasfondo matemático de tal opción? Yo, probablemente aburrido, solo dividiría por 2.
Luis Filipe
3
Porque si un número tiene factores primos, al menos uno de ellos debe ser menor o igual a la raíz cuadrada. Si a * b = cy a <= b entonces a <= sqrt (c) <= b.
David Johnstone
8

debería echar un vistazo a probables números primos . En particular, eche un vistazo a los algoritmos aleatorios y la prueba de primaria de Miller-Rabin .

En aras de la integridad, puede usar java.math.BigInteger :

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}
dfa
fuente
2
Miller-Rabbin es muy rápido y el código es muy simple. Darle suficientes iteraciones lo hace lo suficientemente confiable como para competir con fallas aleatorias de la CPU en términos de probabilidad de un falso positivo. La desventaja del algoritmo es que comprender por qué funciona realmente es una tarea difícil.
Brian
6

De ninguna manera eficiente, pero quizás el más legible:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

con:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

De hecho, solo una variación de algunas publicaciones aquí con un formato más agradable.

RaphM
fuente
5

Derechos de autor 2009 de St. Wittum 13189 Berlín ALEMANIA bajo licencia CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

La forma simple pero más elegante de calcular TODOS LOS PRIMES sería esta, pero de esta manera es lenta y los costos de memoria son mucho más altos para números más altos porque se usa la función de facultad (!) ... generar todos los primos por algoritmo implementado en Python

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)
Steffen Wittum
fuente
4

Utilice un generador de números primos para crear primes.txt y luego:

class Program
{
    static void Main(string[] args)
    {
        using (StreamReader reader = new StreamReader("primes.txt"))
        {
            foreach (var prime in GetPrimes(10, reader))
            {
                Console.WriteLine(prime);
            }
        }
    }

    public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
    {
        int count = 0;
        string line = string.Empty;
        while ((line = reader.ReadLine()) != null && count++ < upTo)
        {
            yield return short.Parse(line);
        }
    }
}

En este caso, utilizo Int16 en la firma del método, por lo que mi archivo primes.txt contiene números del 0 al 32767. Si desea extender esto a Int32 o Int64, su primes.txt podría ser significativamente mayor.

Darin Dimitrov
fuente
3
Citando el OP: "No me importa qué método se use (ingenuo o tamiz o cualquier otra cosa), pero quiero que sea bastante breve y obvio cómo funciona". Creo que mi respuesta es perfectamente relevante. También es el método más rápido.
Darin Dimitrov
14
Incluso si dice "No me importa qué método ...", no creo que eso incluya "abrir una lista de números primos". Eso sería como responder a la pregunta "cómo construir una computadora" con "comprar una computadora". -1
stevenvh
8
Sería más rápido si realmente escribiera los números primos en el código fuente, en lugar de leerlos desde un archivo.
Daniel Daranas
3
¿Consume mucha memoria? más que leer la lista completa de números primos como texto en ... ¿memoria? ¿Sabes cómo funcionan las cadenas en .net?
jmservera
6
La lista de números primos es una lista infinita pero inmutable, por lo que tiene mucho sentido usar una lista precalculada hasta el límite superior probable para la aplicación. ¿Por qué perder el tiempo escribiendo código que puede tener errores cuando hay una lista pública correcta disponible que se puede utilizar para cumplir con los requisitos?
AndyM
4

Puedo ofrecer la siguiente solución de C #. De ninguna manera es rápido, pero es muy claro lo que hace.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    for (int n = 3; n <= limit; n += 2)
    {
        Int32 sqrt = (Int32)Math.Sqrt(n);

        if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
        {
            primes.Add(n);
        }
    }

    return primes;
}

Dejé todos los controles, si el límite es negativo o menor que dos (por el momento, el método siempre devolverá al menos dos como primo). Pero todo eso es fácil de arreglar.

ACTUALIZAR

Con los siguientes dos métodos de extensión

public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        action(item);
    }
}

public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
    for (int i = start; i < end; i += step)
    }
        yield return i;
    }
}

puede reescribirlo de la siguiente manera.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    Range(3, limit, 2)
        .Where(n => primes
            .TakeWhile(p => p <= Math.Sqrt(n))
            .All(p => n % p != 0))
        .Do(n => primes.Add(n));

    return primes;
}

Es menos eficiente (porque la raíz cuadrada se reevalúa con bastante frecuencia) pero es un código aún más limpio. Es posible reescribir el código para enumerar perezosamente los números primos, pero esto saturará un poco el código.

Daniel Brückner
fuente
Estoy casi seguro de que el compilador JIT optimiza el cálculo de la raíz cuadrada (cuando se compila con la optimización habilitada). Tendría que verificar esto examinando el ensamblado generado (el IL está solo parcialmente optimizado y no se acerca a la optimización realizada por el compilador JIT. Los días de elevación de bucles y otras micro optimizaciones han terminado. De hecho, a veces se intenta ser más astuto que el JIT puede ralentizar su código.
Dave Black
4

Aquí hay una implementación de Sieve of Eratosthenes en C #:

    IEnumerable<int> GeneratePrimes(int n)
    {
        var values = new Numbers[n];

        values[0] = Numbers.Prime;
        values[1] = Numbers.Prime;

        for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
        {
            values[outer] = Numbers.Prime;

            for (int inner = outer * 2; inner < values.Length; inner += outer)
                values[inner] = Numbers.Composite;
        }

        for (int i = 2; i < values.Length; i++)
        {
            if (values[i] == Numbers.Prime)
                yield return i;
        }
    }

    int FirstUnset(Numbers[] values, int last)
    {
        for (int i = last; i < values.Length; i++)
            if (values[i] == Numbers.Unset)
                return i;

        return -1;
    }

    enum Numbers
    {
        Unset,
        Prime,
        Composite
    }
Alon Gubkin
fuente
haría eso con un bool en lugar de enum ...
Letterman
3

Usando su mismo algoritmo, puede hacerlo un poco más corto:

List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}
jmservera
fuente
3

Sé que solicitó una solución que no sea de Haskell, pero incluyo esto aquí en lo que respecta a la pregunta y también Haskell es hermoso para este tipo de cosas.

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0
grom
fuente
Sí, también soy un gran fan de Haskell (solo desearía saberlo mejor)
David Johnstone
3

Escribí una implementación simple de Eratóstenes en c # usando algo de LINQ.

Desafortunadamente, LINQ no proporciona una secuencia infinita de entradas, por lo que debe usar int.MaxValue :(

Tuve que almacenar en caché en un tipo anónimo el sqrt candidato para evitar calcularlo para cada primo almacenado en caché (se ve un poco feo).

Utilizo una lista de primos anteriores hasta sqrt del candidato

cache.TakeWhile(c => c <= candidate.Sqrt)

y comprobar cada Int a partir de 2 contra él

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

Aquí está el código:

static IEnumerable<int> Primes(int count)
{
    return Primes().Take(count);
}

static IEnumerable<int> Primes()
{
    List<int> cache = new List<int>();

    var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new 
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

Otra optimización es evitar verificar números pares y devolver solo 2 antes de crear la lista. De esta manera, si el método de llamada solo pide 1 primo, evitará todo el desorden:

static IEnumerable<int> Primes()
{
    yield return 2;
    List<int> cache = new List<int>() { 2 };

    var primes = Enumerable.Range(3, int.MaxValue - 3)
        .Where(candidate => candidate % 2 != 0)
        .Select(candidate => new
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}
Maghis
fuente
1
Ojalá supiera LINQ lo suficiente para apreciar y comprender mejor esta respuesta :-) Además, tengo la sensación de que esto no es una implementación del tamiz de Eratosthenes, y que funciona conceptualmente igual que mi función original (busque el siguiente número que no es divisible por ninguno de los primos encontrados anteriormente).
David Johnstone
Sí, pero "encontrar el siguiente número que no sea divisible por ninguno de los primos encontrados anteriormente (menor que el número)" es conceptualmente similar al tamiz de eratóstenes. Si lo prefiere, puedo refactorizarlo un poco para que sea más legible incluso si no está familiarizado con LINQ. ¿Está familiarizado con los iteradores?
Maghis
Lo que me gusta de este enfoque es que el próximo primo se calcula justo cuando la persona que llama lo solicita, por lo que cosas como "tomar los primeros n números primos" o "tomar los números primos que son más pequeños que n" se vuelven triviales
Maghis
1
Gracias, pero puedo entender eso lo suficiente como para saber más o menos lo que está haciendo :-) Me gusta la evaluación perezosa, pero todavía no llamaría a esto una implementación del tamiz de Eratosthenes.
David Johnstone
1

Para hacerlo más elegante, debe refactorizar su prueba IsPrime en un método separado y manejar el bucle y los incrementos fuera de eso.

cjk
fuente
1

Lo hice en Java usando una biblioteca funcional que escribí, pero como mi biblioteca usa los mismos conceptos que las Enumeraciones, estoy seguro de que el código es adaptable:

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});
Vincent Robert
fuente
1

Este es el más elegante que se me ocurre a corto plazo.

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

Espero que esto ayude a darte una idea. Estoy seguro de que esto se puede optimizar, sin embargo, debería darte una idea de cómo tu versión podría ser más elegante.

EDITAR: Como se señaló en los comentarios, este algoritmo de hecho devuelve valores incorrectos para numberToGenerate <2. Solo quiero señalar que no estaba tratando de publicarle un gran método para generar números primos (mire la respuesta de Henri para eso), Al principio estaba señalando cómo su método podría ser más elegante.

David Božjak
fuente
3
Éste devuelve un resultado incorrecto para numberToGenerate <2
Peter Smit
Esto es cierto, sin embargo, no estaba diseñando un algoritmo, solo le estaba mostrando cómo su método puede hacerse más elegante. Así que esta versión es igualmente errónea que la de la pregunta inicial.
David Božjak
1
No se me ocurrió que estaba roto por n = 1. Cambié la pregunta ligeramente para que la función solo funcione para n> 1 :-)
David Johnstone
esto admite cuadrados de primos como números primos.
Will Ness
1

Usando programación basada en flujo en Functional Java , se me ocurrió lo siguiente. El tipo Naturales esencialmente a BigInteger> = 0.

public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
  { public Stream<Natural> _1()
    { return sieve(xs.tail()._1()
                   .filter($(naturalOrd.equal().eq(ZERO))
                           .o(mod.f(xs.head())))); }}); }

public static final Stream<Natural> primes
  = sieve(forever(naturalEnumerator, natural(2).some()));

Ahora tiene un valor, que puede llevar consigo, que es un flujo infinito de números primos. Puedes hacer cosas como esta:

// Take the first n primes
Stream<Natural> nprimes = primes.take(n);

// Get the millionth prime
Natural mprime = primes.index(1000000);

// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));

Una explicación del tamiz:

  1. Suponga que el primer número en el flujo de argumentos es primo y colóquelo al principio del flujo de retorno. El resto del flujo de retorno es un cálculo que se producirá solo cuando se solicite.
  2. Si alguien pregunta por el resto del flujo, llame a tamiz en el resto del flujo de argumentos, filtrando los números divisibles por el primer número (el resto de la división es cero).

Necesita tener las siguientes importaciones:

import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
Apocalipsis
fuente
1

Personalmente, creo que esta es una implementación bastante corta y limpia (Java):

static ArrayList<Integer> getPrimes(int numPrimes) {
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    int n = 2;
    while (primes.size() < numPrimes) {
        while (!isPrime(n)) { n++; }
        primes.add(n);
        n++;
    }
    return primes;
}

static boolean isPrime(int n) {
    if (n < 2) { return false; }
    if (n == 2) { return true; }
    if (n % 2 == 0) { return false; }
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) { return false; }
        d += 2;
    }
    return true;
}
Zarkonnen
fuente
1

Pruebe esta consulta LINQ, genera números primos como esperaba

        var NoOfPrimes= 5;
        var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
          .Where(x =>
            {
                 return (x==1)? false:
                        !Enumerable.Range(1, (int)Math.Sqrt(x))
                        .Any(z => (x % z == 0 && x != z && z != 1));
            }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();
RameshVel
fuente
1
// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);

// Sequential prime number generator
var primes_ = from n in range
     let w = (int)Math.Sqrt(n)
     where Enumerable.Range(2, w).All((i) => n % i > 0)
     select n;

// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
    Trace.Write(p + ", ");
Trace.WriteLine("");
Raj Parmar
fuente
0

Aquí hay un ejemplo de código de Python que imprime la suma de todos los números primos por debajo de dos millones:

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum
grom
fuente
0

El método más simple es el de prueba y error: pruebe si cualquier número entre 2 y n-1 divide su candidato primo n.
Los primeros atajos son, por supuesto, a) solo tiene que verificar los números impares, yb) solo tiene que verificar los divisores hasta sqrt (n).

En su caso, donde también genera todos los primos anteriores en el proceso, solo tiene que verificar si alguno de los primos en su lista, hasta sqrt (n), divide n.
Debería ser lo más rápido que pueda obtener por su dinero :-)

editar
Ok, código, lo pediste. Pero te advierto :-), este es un código Delphi rápido y sucio de 5 minutos:

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;
stevenvh
fuente
1
¿Y cómo se expresa esto en código? :-)
David Johnstone
0

Para averiguar los primeros 100 números primos, se puede considerar el siguiente código java.

int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;

    do
    {

        for (i = 2; i <num; i++)
        {

             int n = num % i;

             if (n == 0) {

             nPrimeCount++;
         //  System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);

             num++;
             break;

             }
       }

                if (i == num) {

                    primeCount++;

                    System.out.println(primeCount + " " + "Prime number is: " + num);
                    num++;
                }


     }while (primeCount<100);
Zakir Sajib
fuente
0

Lo obtuve leyendo por primera vez "Sieve of Atkin" en Wikki, además de un pensamiento previo que le he dado a esto: paso mucho tiempo codificando desde cero y me fijo completamente en que la gente sea crítica con mi codificación muy densa, similar a un compilador style + Ni siquiera he hecho un primer intento de ejecutar el código ... muchos de los paradigmas que he aprendido a usar están aquí, solo lee y llora, consigue lo que puedas.

Esté absolutamente y totalmente seguro de probar todo esto antes de cualquier uso, seguro que no se lo muestre a nadie, es para leer y considerar las ideas. Necesito que la herramienta de primalidad funcione, así que aquí es donde comienzo cada vez que tengo que hacer que algo funcione.

Obtenga una compilación limpia, luego comience a eliminar lo que está defectuoso: tengo casi 108 millones de pulsaciones de teclas de código utilizable haciéndolo de esta manera, ... use lo que pueda.

Trabajaré en mi versión mañana.

package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;

/**
 * May we start by ignores any numbers divisible by two, three, or five
 * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
 * these may be done by hand. Then, with some thought we can completely
 * prove to certainty that no number larger than square-root the number
 * can possibly be a candidate prime.
 */

public class PrimeGenerator<T>
{
    //
    Integer HOW_MANY;
    HashSet<Integer>hashSet=new HashSet<Integer>();
    static final java.lang.String LINE_SEPARATOR
       =
       new java.lang.String(java.lang.System.getProperty("line.separator"));//
    //
    PrimeGenerator(Integer howMany) throws GeneralSecurityException
    {
        if(howMany.intValue() < 20)
        {
            throw new GeneralSecurityException("I'm insecure.");
        }
        else
        {
            this.HOW_MANY=howMany;
        }
    }
    // Let us then take from the rich literature readily 
    // available on primes and discount
    // time-wasters to the extent possible, utilizing the modulo operator to obtain some
    // faster operations.
    //
    // Numbers with modulo sixty remainder in these lists are known to be composite.
    //
    final HashSet<Integer> fillArray() throws GeneralSecurityException
    {
        // All numbers with modulo-sixty remainder in this list are not prime.
        int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
        32,34,36,38,40,42,44,46,48,50,52,54,56,58};        //
        for(int nextInt:list1)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list1");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are  are
        // divisible by three and not prime.
        int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
        //
        for(int nextInt:list2)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list2");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are
        // divisible by five and not prime. not prime.
        int[]list3=new int[]{5,25,35,55};
        //
        for(int nextInt:list3)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list3");//
            }
        }
        // All numbers with modulo-sixty remainder in
        // this list have a modulo-four remainder of 1.
        // What that means, I have neither clue nor guess - I got all this from
        int[]list4=new int[]{1,13,17,29,37,41,49,53};
        //
        for(int nextInt:list4)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list4");//
            }
        }
        Integer lowerBound=new Integer(19);// duh
        Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
        int upperBound=upperStartingPoint.intValue();//
        HashSet<Integer> resultSet=new HashSet<Integer>();
        // use a loop.
        do
        {
            // One of those one liners, whole program here:
            int aModulo=upperBound % 60;
            if(this.hashSet.contains(new Integer(aModulo)))
            {
                continue;
            }
            else
            {
                resultSet.add(new Integer(aModulo));//
            }
        }
        while(--upperBound > 20);
        // this as an operator here is useful later in your work.
        return resultSet;
    }
    // Test harness ....
    public static void main(java.lang.String[] args)
    {
        return;
    }
}
//eof
Nicolás Jordan
fuente
0

Prueba este código.

protected bool isPrimeNubmer(int n)
    {
        if (n % 2 == 0)
            return false;
        else
        {
            int j = 3;
            int k = (n + 1) / 2 ;

            while (j <= k)
            {
                if (n % j == 0)
                    return false;
                j = j + 2;
            }
            return true;
        }
    }
    protected void btn_primeNumbers_Click(object sender, EventArgs e)
    {
        string time = "";
        lbl_message.Text = string.Empty;
        int num;

        StringBuilder builder = new StringBuilder();

        builder.Append("<table><tr>");
        if (int.TryParse(tb_number.Text, out num))
        {
            if (num < 0)
                lbl_message.Text = "Please enter a number greater than or equal to 0.";
            else
            {
                int count = 1;
                int number = 0;
                int cols = 11;

                var watch = Stopwatch.StartNew();

                while (count <= num)
                {
                    if (isPrimeNubmer(number))
                    {
                        if (cols > 0)
                        {
                            builder.Append("<td>" + count + " - " + number + "</td>");
                        }
                        else
                        {
                            builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
                            cols = 11;
                        }
                        count++;
                        number++;
                        cols--;
                    }
                    else
                        number++;
                }
                builder.Append("</table>");
                watch.Stop();
                var elapsedms = watch.ElapsedMilliseconds;
                double seconds = elapsedms / 1000;
                time = seconds.ToString();
                lbl_message.Text = builder.ToString();
                lbl_time.Text = time;
            }
        }
        else
            lbl_message.Text = "Please enter a numberic number.";

        lbl_time.Text = time;

        tb_number.Text = "";
        tb_number.Focus();
    }

Aquí está el código aspx.

<form id="form1" runat="server">
    <div>
        <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>

        <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
        </p>
        <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
        <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
    </div>
</form>

Resultados: 10000 números primos en menos de un segundo

100000 números primos en 63 segundos

Captura de pantalla de los primeros 100 números primos ingrese la descripción de la imagen aquí

riz
fuente
1
Probándolo, pude medir su efectividad y presentación de resultados: por favor discuta su elegancia.
barba gris
El estilo del resultado es solo una parte adicional. Permítanme discutir el algoritmo para devolver verdadero / falso como número primo. n% 2 eliminará la mitad de los números porque los números pares siempre son divisibles por 2. En el código else, estoy dividiendo solo por números impares, aumentando el divisible por dos (por lo que el siguiente divisible también es impar) hasta la mitad de ese número que es primo o no. Por qué la mitad, para no perder el tiempo porque nos dará respuesta en fracción.
riz
log10 (63) ~ = 1.8, es decir, sus datos muestran una tasa de crecimiento de n ^ 1.8. Esto es muy lento; tamiz óptimo de implementaciones de Eratóstenes exibit ~ n ^ 1.01..1.05; división de prueba óptima ~ n ^ 1.35..1.45. De isPrimeNubmerhecho, implementa la división tril subóptima; sus asintóticos empeorarán a aproximadamente n ^ 2 (o incluso más) cuando intente generar aún más números primos.
Will Ness