Die eleganteste Art, Primzahlen zu erzeugen [closed]

Was ist der eleganteste Weg, diese Funktion zu implementieren:

ArrayList generatePrimes(int n)

Diese Funktion generiert die erste n Primzahlen (Bearbeiten: wo n>1), Also generatePrimes(5) wird ein zurückgeben ArrayList mit {2, 3, 5, 7, 11}. (Ich mache das in C #, aber ich bin mit einer Java-Implementierung zufrieden – oder einer anderen ähnlichen Sprache für diese Angelegenheit (also nicht Haskell)).

Ich weiß, wie man diese Funktion schreibt, aber als ich es letzte Nacht gemacht habe, war es nicht so schön, wie ich gehofft hatte. Hier ist, was ich herausgefunden habe:

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

Ich mache mir keine allzu großen Sorgen um die Geschwindigkeit, obwohl ich nicht möchte, dass sie offensichtlich ineffizient ist. Es ist mir egal, welche Methode verwendet wird (naiv oder Sieb oder irgendetwas anderes), aber ich möchte, dass es ziemlich kurz und offensichtlich ist, wie es funktioniert.

Bearbeiten: Danke an alle, die geantwortet haben, obwohl viele meine eigentliche Frage nicht beantwortet haben. Um es noch einmal zu wiederholen, ich wollte ein nettes, sauberes Stück Code, das eine Liste von Primzahlen generiert. Ich weiß bereits, wie man es auf verschiedene Arten macht, aber ich neige dazu, Code zu schreiben, der nicht so klar ist, wie er sein könnte. In diesem Thread wurden einige gute Optionen vorgeschlagen:

• Eine schönere Version dessen, was ich ursprünglich hatte (Peter Smit, jmservera und Rekreativc)
• Eine sehr saubere Umsetzung des Siebes von Eratosthenes (starblue)
• Verwenden Sie Javas BigIntegers und nextProbablePrime für sehr einfachen Code, obwohl ich mir nicht vorstellen kann, dass er besonders effizient ist (dfa)
• Verwenden Sie LINQ, um die Liste der Primzahlen träge zu generieren (Maghis)
• Viele Primzahlen in eine Textdatei schreiben und bei Bedarf einlesen (darin)

Bearbeiten 2Hinweis: Ich habe in C# einige der hier angegebenen Methoden und eine weitere Methode implementiert, die hier nicht erwähnt wird. Sie alle finden den ersten n Primzahlen effektiv (und ich habe eine anständige Methode, um die Grenze für die Siebe zu finden).

Verwenden Sie die Schätzung

pi(n) = n / log(n)

für die Anzahl der Primzahlen bis n eine Grenze finden und dann ein Sieb verwenden. Die Schätzung unterschätzt die Anzahl der Primzahlen bis n etwas, sodass das Sieb etwas größer als nötig ist, was in Ordnung ist.

Dies ist mein Standard-Java-Sieb, das auf einem normalen Laptop die erste Million Primzahlen in etwa einer Sekunde berechnet:

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

Vielen Dank an alle, die hilfreiche Antworten gegeben haben. Hier sind meine Implementierungen einiger verschiedener Methoden, um die erste zu finden n Primzahlen in C#. Die ersten beiden Methoden sind so ziemlich das, was hier gepostet wurde. (Die Namen der Poster stehen neben dem Titel.) Ich plane, irgendwann das Sieb von Atkin zu machen, obwohl ich vermute, dass es nicht ganz so einfach sein wird wie die Methoden hier derzeit. Wenn jemand eine Möglichkeit sieht, eine dieser Methoden zu verbessern, würde ich es gerne wissen 🙂

Standardmethode (Peter Smit, jmservera, Rekreative)

Die erste Primzahl ist 2. Fügen Sie diese zu einer Liste von Primzahlen hinzu. Die nächste Primzahl ist die nächste Zahl, die durch keine Zahl auf dieser Liste ohne Rest teilbar ist.

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

Dies wurde optimiert, indem nur auf Teilbarkeit bis zur Quadratwurzel der getesteten Zahl getestet wurde; und indem nur ungerade Zahlen getestet werden. Dies kann weiter optimiert werden, indem nur Zahlen des Formulars getestet werden 6k+[1, 5]oder 30k+[1, 7, 11, 13, 17, 19, 23, 29] oder bald.

Sieb des Eratosthenes (sternblau)

Dies findet alle Primzahlen zu k. Um eine Liste der ersten zu machen n Primzahlen, müssen wir zuerst den Wert von approximieren nte Primzahl. Die folgende Methode, wie hier beschrieben, tut dies.

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

Sieb von Sundaram

Ich habe nur entdeckt dieses Sieb vor kurzem, aber es kann ganz einfach implementiert werden. Meine Implementierung ist nicht so schnell wie das Sieb des Eratosthenes, aber deutlich schneller als die naive Methode.

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

Wiederbelebung einer alten Frage, aber ich bin beim Spielen mit LINQ darüber gestolpert.

Dieser Code erfordert .NET4.0 oder .NET3.5 mit parallelen Erweiterungen

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

Du bist auf dem guten Weg.

Einige Kommentare

• primes.Add(3); bewirkt, dass diese Funktion für Zahl = 1 nicht funktioniert

• Sie müssen die Division nicht mit Primzahlen testen, die größer sind als die Quadratwurzel der zu testenden Zahl.

Vorgeschlagener Code:

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

solltest du dir mal anschauen wahrscheinliche Primzahlen. Schauen Sie sich insbesondere an Randomisierte Algorithmen und Miller-Rabin-Primzahltest.

Der Vollständigkeit halber könnte man einfach verwenden 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);
    }
}

Auf keinen Fall effizient, aber vielleicht am lesbarsten:

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

mit:

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

Eigentlich nur eine Variation einiger Beiträge hier mit schönerer Formatierung.

Copyrights 2009 by St.Wittum 13189 Berlin DEUTSCHLAND unter CC-BY-SA Lizenz
https://creativecommons.org/licenses/by-sa/3.0/

Der einfachste, aber eleganteste Weg, ALLE PRIMES zu berechnen, wäre dieser Weg, aber dieser Weg ist langsam und die Speicherkosten sind für höhere Zahlen viel höher, weil die Fakultätsfunktion (!) verwendet wird … aber es demonstriert eine Variation des Wilson-Theorems in einer Anwendung zu Erzeuge alle Primzahlen durch einen in Python implementierten Algorithmus

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