Die eleganteste Art, Primzahlen zu generieren [geschlossen]

83

Was ist der eleganteste Weg, um diese Funktion zu implementieren:

ArrayList generatePrimes(int n)

Diese Funktion generiert die ersten nPrimzahlen (edit: where n>1) und gibt daher generatePrimes(5)ein ArrayListwith zurück {2, 3, 5, 7, 11}. (Ich mache das in C #, aber ich bin zufrieden mit einer Java-Implementierung - oder einer anderen ähnlichen Sprache (also nicht Haskell)).

Ich weiß, wie man diese Funktion schreibt, aber als ich sie letzte Nacht gemacht habe, war sie nicht so schön, wie ich es mir erhofft hatte. Folgendes habe ich mir ausgedacht:

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 macht mir nichts aus, welche Methode verwendet wird (naiv oder Sieb oder irgendetwas anderes), aber ich möchte, dass es ziemlich kurz und offensichtlich ist, wie es funktioniert.

Edit : Danke an alle, die geantwortet haben, obwohl viele meine eigentliche Frage nicht beantwortet haben. Um es noch einmal zu wiederholen, ich wollte einen schönen, sauberen Code, der 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 von dem, was ich ursprünglich hatte (Peter Smit, jmservera und Rekreativc)
  • Eine sehr saubere Umsetzung des Siebsosthenes (Sternenblau)
  • Verwenden Sie Java BigIntegerund nextProbablePrimefür sehr einfachen Code, obwohl ich mir nicht vorstellen kann, dass er besonders effizient ist (dfa).
  • Verwenden Sie LINQ, um die Liste der Primzahlen (Maghis) träge zu erstellen.
  • Fügen Sie viele Primzahlen in eine Textdatei ein und lesen Sie sie bei Bedarf ein.

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

David Johnstone
quelle
12
Nein, und es ist auch nicht für Project Euler :-)
David Johnstone
1
Es wäre besser, wenn ich unzählige <int> wiederholen und eins nach dem anderen nachgeben würde
Felice Pollano
4
Was ich gerne wissen würde, ist die am wenigsten elegante Art, Primzahlen zu generieren. Ich denke an eine Access-Datenbank?
j_random_hacker
1
zum Vergleich ein 2008er Haskell-Code von BMeph : nubBy (((>1).).gcd) [2..]. Es bleiben nur Nicht-Duplikate unter den natürlichen Zahlen, beginnend mit 2, während jede Zahl, deren gcdmit einer der zuvor gefundenen Zahlen größer als 1 ist, als Duplikat betrachtet wird. Es ist sehr ineffizient und quadratisch in der Anzahl der produzierten Primzahlen. Aber es ist elegant .
Will Ness
Das eleganteste , IMO, ist das von 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..]) ) }aber das basiert natürlich ausschließlich auf Meinungen .
Will Ness

Antworten:

48

Verwenden Sie die Schätzung

pi(n) = n / log(n)

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

Dies ist mein Standard-Java-Sieb, das die ersten Millionen Primzahlen in etwa einer Sekunde auf einem normalen Laptop 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;
}
Sternenblau
quelle
3
Das ist eine sehr schöne Implementierung des Siebs von Eratosthenes
David Johnstone
1
Sollte es nicht ausreichen, i <= Math.sqrt(limit)in der äußeren Schleife zu schleifen?
Christoph
1
@ David Johnstone Nein, pi (n) = n / log (n) unterschätzt die Anzahl der Primzahlen bis zu n, was in die entgegengesetzte Richtung geht. Ich bin froh, dass Sie eine viel schönere Annäherung gefunden haben.
Starblue
1
Wenn Sie bereit sind, alle Vielfachen von 2 in einer eigenen Schleife zu entfernen, können Sie j + = 2 * i als Schleifeninkrement verwenden, um zusätzliche Laufzeit zu sparen, und Sie können dies einmal mit einer Bitverschiebung berechnen
Nick Larsen,
5
Durch das Ersetzen BitSetdurch eine Klasse, die die Radfaktorisierung für 2, 3 und 5 implementiert, wird sie fast dreimal schneller.
Starblue
37

Vielen Dank an alle, die hilfreiche Antworten gegeben haben. Hier sind meine Implementierungen einiger verschiedener Methoden zum Finden der ersten 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 habe vor, irgendwann das Sieb von Atkin zu machen, obwohl ich vermute, dass es nicht ganz so einfach ist wie die Methoden hier derzeit. Wenn jemand eine Möglichkeit sieht, eine dieser Methoden zu verbessern, würde ich gerne wissen :-)

Standardmethode ( Peter Smit , jmservera , Rekreativc )

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 in dieser Liste gleichmäßig 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 die Teilbarkeit bis zur Quadratwurzel der getesteten Zahl getestet wurde. und indem nur ungerade Zahlen getestet werden. Dies kann durch nur Testen optimiert werden Zahlen der Form 6k+[1, 5], oder 30k+[1, 7, 11, 13, 17, 19, 23, 29]oder so weiter .

Sieb von Eratosthenes ( Sternenblau )

Dies findet alle Primzahlen zu k . Um eine Liste der ersten n Primzahlen zu erstellen, müssen wir zuerst den Wert der n- ten Primzahl approximieren . Die folgende Methode, wie hier beschrieben , führt dies aus.

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 dieses Sieb erst kürzlich entdeckt, aber es kann ganz einfach implementiert werden. Meine Implementierung ist nicht so schnell wie das Sieb von 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;
}
David Johnstone
quelle
Zu Ihrer Information - Ich musste Ihren Hauptschleifenzähler auf "for (int i = 0; i * i <= limit && i * i> 0; i ++)" ändern, um einen Überlauf zu verhindern.
Jacobs Data Solutions
Diese Implementierung des Siebs von Sundaram ist eine der wenigen richtigen, die es gibt. Die meisten von ihnen verwenden bei der Berechnung falsche Grenzen für i und j, i+j+2*i*jwas zu einer falschen Ausgabe führt.
Jahackbeth
13

Ich habe eine alte Frage wiederbelebt, bin aber 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();
}
Spookycoder
quelle
1
Warum ist das nicht die akzeptierte Antwort? Der Code hier ist viel kürzer, eleganter und viel schneller als der Code in der akzeptierten Antwort. Ich wünschte, ich könnte mehr als einmal abstimmen!
Avrohom Yisroel
9

Du bist auf dem guten Weg.

Einige Kommentare

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

  • Sie müssen die Division nicht mit Primzahlen testen, die größer sind als der 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;
}
Peter Smit
quelle
1
Das Testen dieses prime * prime <= curTest in der Schleife anstelle der Vorausberechnung der Quadratwurzel wird sie wahrscheinlich schneller und allgemeiner machen (funktioniert für Bignums usw.)
yairchu
Warum die Quadratwurzel verwenden? Was ist der mathematische Hintergrund für eine solche Option? Ich, wahrscheinlich dumpf, würde nur durch 2 teilen.
Luis Filipe
3
Denn wenn eine Zahl Primfaktoren hat, muss mindestens einer kleiner oder gleich der Quadratwurzel sein. Wenn a * b = c und a <= b, dann ist a <= sqrt (c) <= b.
David Johnstone
8

Sie sollten einen Blick auf wahrscheinliche Primzahlen werfen . Schauen Sie sich insbesondere Randomisierte Algorithmen und den Miller-Rabin-Primalitätstest an .

Der Vollständigkeit halber können Sie einfach java.math.BigInteger verwenden :

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
quelle
2
Miller-Rabbin ist sehr schnell und der Code ist sehr einfach. Wenn es ausreichend iteriert wird, ist es zuverlässig genug, um im Hinblick auf die Wahrscheinlichkeit eines falsch positiven Ergebnisses mit einem zufälligen CPU-Ausfall zu konkurrieren. Der Nachteil des Algorithmus ist, dass es schwierig ist zu verstehen, warum er tatsächlich funktioniert.
Brian
6

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

In der Tat nur eine Variation einiger Beiträge hier mit schönerer Formatierung.

RaphM
quelle
5

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

Der einfachste, aber eleganteste Weg, ALLE PRIMEN zu berechnen, wäre dieser, 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 zeigt eine Variation des Wilson-Theorems in einer Anwendung auf Generieren Sie alle Primzahlen mit einem 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)
Steffen Wittum
quelle
4

Verwenden Sie eine erstklassige Zahlen Generator primes.txt zu erstellen und dann:

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

In diesem Fall verwende ich Int16 in der Methodensignatur, daher enthält meine Datei primes.txt Zahlen von 0 bis 32767. Wenn Sie dies auf Int32 oder Int64 erweitern möchten, kann Ihre Datei primes.txt erheblich größer sein.

Darin Dimitrov
quelle
3
Zitieren des OP: "Es macht mir nichts aus, welche Methode verwendet wird (naiv oder Sieb oder irgendetwas anderes), aber ich möchte, dass es ziemlich kurz und offensichtlich ist, wie es funktioniert." Ich denke, meine Antwort ist absolut relevant. Es ist auch die schnellste Methode.
Darin Dimitrov
14
Selbst wenn er sagt "Es macht mir nichts aus, welche Methode ...", denke ich nicht, dass dies "eine Liste von Primzahlen öffnen" beinhaltet. Das wäre wie die Beantwortung der Frage "Wie baue ich einen Computer?" Mit "Kauf eines Computers". -1
Stevenvh
8
Es wäre schneller, wenn Sie die Primzahlen tatsächlich im Quellcode selbst schreiben würden, anstatt sie aus einer Datei zu lesen.
Daniel Daranas
3
Viel Speicher verbrauchen? mehr als das Lesen der vollständigen Primzahlliste als Text in ... Speicher? Wissen Sie, wie Strings in .net funktionieren?
jmservera
6
Die Liste der Primzahlen ist eine unendliche, aber unveränderliche Liste, daher ist es absolut sinnvoll, eine vorberechnete Liste bis zur wahrscheinlichen Obergrenze für die Anwendung zu verwenden. Warum Zeit damit verschwenden, Code zu schreiben, der möglicherweise fehlerhaft ist, wenn eine korrekte öffentliche Liste verfügbar ist, mit der die Anforderungen erfüllt werden können?
AndyM
4

Ich kann die folgende C # -Lösung anbieten. Es ist keineswegs schnell, aber es ist sehr klar, was es tut.

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

Ich habe alle Überprüfungen ausgelassen - wenn das Limit negativ oder kleiner als zwei ist (im Moment gibt die Methode immer mindestens zwei als Primzahl zurück). Aber das ist alles leicht zu beheben.

AKTUALISIEREN

Mit den folgenden zwei Erweiterungsmethoden

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

Sie können es wie folgt umschreiben.

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 ist weniger effizient (weil die Quadratwurzel ziemlich oft neu bewertet wird), aber es ist noch sauberer Code. Es ist möglich, den Code neu zu schreiben, um die Primzahlen träge aufzulisten, aber dies wird den Code ziemlich durcheinander bringen.

Daniel Brückner
quelle
Ich bin mir fast sicher, dass die Berechnung der Quadratwurzel vom JIT-Compiler optimiert wird (wenn sie mit aktivierter Optimierung kompiliert wird). Sie müssten dies überprüfen, indem Sie die generierte Baugruppe untersuchen (die IL ist nur teilweise optimiert und entspricht nicht annähernd der vom JIT-Compiler durchgeführten Optimierung. Die Tage des Loop-Hebens und anderer Mikrooptimierungen sind längst vorbei Überlisten Sie die JIT kann Ihren Code verlangsamen .
Dave Black
4

Hier ist eine Implementierung von Sieve of Eratosthenes in 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
quelle
Ich würde das mit einem Bool anstelle von Enum machen ...
Letterman
3

Mit demselben Algorithmus können Sie es etwas kürzer machen:

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
quelle
3

Ich weiß, dass Sie nach einer Nicht-Haskell-Lösung gefragt haben, aber ich füge diese hier ein, da sie sich auf die Frage bezieht, und auch Haskell ist für diese Art von Dingen wunderschön.

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
quelle
Ja, ich bin auch ein großer Fan von Haskell (ich wünschte nur, ich wüsste es besser)
David Johnstone
3

Ich habe eine einfache Eratosthenes-Implementierung in c # mit etwas LINQ geschrieben.

Leider bietet LINQ keine unendliche Folge von Ints, so dass Sie int.MaxValue :( verwenden müssen

Ich musste den Kandidaten sqrt in einem anonymen Typ zwischenspeichern, um zu vermeiden, dass er für jede zwischengespeicherte Primzahl berechnet wird (sieht etwas hässlich aus).

Ich verwende eine Liste früherer Primzahlen bis zum Quadrat des Kandidaten

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

und überprüfe jedes Int ab 2 dagegen

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

Hier ist der Code:

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

Eine weitere Optimierung besteht darin, zu vermeiden, dass gerade Zahlen überprüft werden, und nur 2 zurückzugeben, bevor die Liste erstellt wird. Auf diese Weise wird, wenn die aufrufende Methode nur nach 1 Primzahl fragt, das ganze Chaos vermieden:

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
quelle
1
Ich wünschte, ich wüsste LINQ genug, um diese Antwort besser zu verstehen und zu verstehen :-) Außerdem habe ich das Gefühl, dass dies keine Implementierung des Eratosthenes-Siebs ist und dass es konzeptionell genauso funktioniert wie meine ursprüngliche Funktion (finden Sie die nächste Zahl, die durch keine der zuvor gefundenen Primzahlen teilbar ist).
David Johnstone
Ja, aber "Finde die nächste Zahl, die nicht durch eine der zuvor gefundenen Primzahlen teilbar ist (kleiner als die Zahl)" ähnelt konzeptionell dem Eratosthenensieb. Wenn Sie es vorziehen, kann ich es ein wenig umgestalten, um es besser lesbar zu machen, auch wenn Sie nicht mit LINQ vertraut sind. Kennen Sie sich mit Iteratoren aus?
Maghis
Was mir an diesem Ansatz gefällt, ist, dass die nächste Primzahl genau dann berechnet wird, wenn der Anrufer danach fragt. Dinge wie "nimm die ersten n Primzahlen" oder "nimm die Primzahlen, die kleiner als n sind" werden trivial
Maghis
1
Danke, aber ich kann das genug verstehen, um mehr oder weniger zu wissen, was es tut :-) Ich mag die faule Bewertung, aber ich würde dies immer noch nicht als Implementierung des Eratosthenes-Siebs bezeichnen.
David Johnstone
1

Um es eleganter zu gestalten, sollten Sie Ihren IsPrime-Test in eine separate Methode umgestalten und die Schleifen und Inkremente außerhalb dieser Methode behandeln.

cjk
quelle
1

Ich habe es in Java mit einer von mir geschriebenen Funktionsbibliothek gemacht, aber da meine Bibliothek dieselben Konzepte wie Aufzählungen verwendet, bin ich sicher, dass der Code anpassbar ist:

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
quelle
1

Dies ist das eleganteste, an das ich kurzfristig denken kann.

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

Hoffe das hilft dir eine Idee zu geben. Ich bin sicher, dass dies optimiert werden kann, aber es sollte Ihnen eine Idee geben, wie Ihre Version eleganter gestaltet werden könnte.

BEARBEITEN: Wie in den Kommentaren erwähnt, gibt dieser Algorithmus tatsächlich falsche Werte für numberToGenerate <2 zurück. Ich möchte nur darauf hinweisen, dass ich nicht versucht habe, ihm eine großartige Methode zum Generieren von Primzahlen zu veröffentlichen (siehe Henrys Antwort darauf). Ich habe mürrisch darauf hingewiesen, wie seine Methode eleganter gestaltet werden könnte.

David Božjak
quelle
3
Dieser gibt ein falsches Ergebnis für numberToGenerate <2
Peter Smit
Dies ist wahr, aber ich habe keinen Algorithmus entworfen, sondern ihm nur gezeigt, wie seine Methode eleganter gestaltet werden kann. Diese Version ist also genauso falsch wie die in der Eröffnungsfrage.
David Božjak
1
Mir ist nicht in den Sinn gekommen, dass es für n = 1 gebrochen war. Ich habe die Frage leicht geändert, so dass die Funktion nur für n> 1 funktionieren muss :-)
David Johnstone
dies lässt Quadrate von Primzahlen als Primzahlen zu.
Will Ness
1

Mit der Stream-basierten Programmierung in Functional Java habe ich Folgendes gefunden. Der Typ Naturalist im Wesentlichen 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()));

Jetzt haben Sie einen Wert, den Sie herumtragen können, der ein unendlicher Strom von Primzahlen ist. Sie können solche Dinge tun:

// 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));

Eine Erklärung des Siebs:

  1. Angenommen, die erste Zahl im Argumentstrom ist eine Primzahl, und setzen Sie sie an die Vorderseite des Rücklaufstroms. Der Rest des Rückstroms ist eine Berechnung, die nur auf Anfrage erstellt werden kann.
  2. Wenn jemand nach dem Rest des Streams fragt, rufen Sie den Rest des Argument-Streams auf und filtern Sie die durch die erste Zahl teilbaren Zahlen heraus (der Rest der Division ist Null).

Sie müssen die folgenden Importe haben:

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;
Apocalisp
quelle
1

Ich persönlich denke, dies ist eine ziemlich kurze und saubere (Java) Implementierung:

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
quelle
1

Probieren Sie diese LINQ-Abfrage aus. Sie generiert wie erwartet Primzahlen

        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
quelle
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
quelle
0

Hier ist ein Python-Codebeispiel, das die Summe aller Primzahlen unter zwei Millionen ausgibt:

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
quelle
0

Die einfachste Methode ist das Ausprobieren: Sie versuchen, ob eine Zahl zwischen 2 und n-1 die Primzahl n Ihres Kandidaten teilt.
Die ersten Verknüpfungen sind natürlich a) Sie müssen nur ungerade Zahlen überprüfen und b) Sie müssen nur nach Teilern bis zu sqrt (n) suchen.

In Ihrem Fall, in dem Sie auch alle vorherigen Primzahlen im Prozess generieren, müssen Sie nur prüfen, ob eine der Primzahlen in Ihrer Liste bis zu sqrt (n) n teilt.
Sollte der schnellste sein, den du für dein Geld bekommen kannst :-)

edit
Ok, Code, du hast danach gefragt. Aber ich warne Sie :-), das ist ein 5-Minuten-Delphi-Code:

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
quelle
1
Und wie drückt man das im Code aus? :-)
David Johnstone
0

Um die ersten 100 Primzahlen herauszufinden, kann der folgende Java-Code berücksichtigt werden.

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
quelle
0

Ich habe dies durch die erste Lesung von "Sieve of Atkin" auf Wikki und einige frühere Überlegungen dazu erhalten - ich verbringe viel Zeit damit, von Grund auf neu zu programmieren, und werde völlig darauf konzentriert, dass Leute meine compilerähnliche, sehr dichte Codierung kritisieren style + Ich habe noch nicht einmal einen ersten Versuch unternommen, den Code auszuführen ... viele der Paradigmen, die ich gelernt habe, sind hier, lesen Sie einfach und weinen Sie, bekommen Sie, was Sie können.

Seien Sie absolut und absolut sicher, dass Sie dies alles wirklich testen, bevor Sie es verwenden. Zeigen Sie es auf keinen Fall jemandem - es dient zum Lesen und Überlegen der Ideen. Ich muss das Primality-Tool zum Laufen bringen, damit ich jedes Mal anfange, wenn ich etwas zum Laufen bringen muss.

Holen Sie sich eine saubere Kompilierung und entfernen Sie dann das, was defekt ist. Ich habe fast 108 Millionen Tastenanschläge mit verwendbarem Code, die dies auf diese Weise tun. Verwenden Sie, was Sie können.

Ich werde morgen an meiner Version arbeiten.

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
Nicholas Jordan
quelle
0

Versuchen Sie diesen Code.

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

Hier ist der Aspx-Code.

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

Ergebnisse: 10000 Primzahlen in weniger als einer Sekunde

100000 Primzahlen in 63 Sekunden

Screenshot der ersten 100 Primzahlen Geben Sie hier die Bildbeschreibung ein

Riz
quelle
1
Wenn ich es versuche, kann ich seine Wirksamkeit und Präsentation von Resutls messen: Bitte argumentieren Sie seine Eleganz.
Graubart
Das Styling des Ergebnisses ist nur ein zusätzlicher Teil. Lassen Sie mich den Algorithmus für die Rückgabe von true / false als Primzahl diskutieren. n% 2 eliminiert die Hälfte der Zahlen, da gerade Zahlen immer durch 2 teilbar sind. Im anderen Code dividiere ich nur durch ungerade Zahlen und erhöhe die Teilbarkeit durch zwei (so dass die nächste teilbare Zahl auch ungerade ist) bis zur Hälfte dieser Zahl, die Primzahl ist oder nicht. Warum die Hälfte, um keine Zeit zu verschwenden, weil es uns eine Antwort in Bruchteilen geben wird.
Riz
log10 (63) ~ = 1,8, dh Ihre Daten zeigen eine Wachstumsrate von n ^ 1,8. Das ist sehr langsam; optimales Sieb von Eratosthenes-Implementierungen exibit ~ n ^ 1.01..1.05; optimale Versuchsteilung ~ n ^ 1.35..1.45. Sie isPrimeNubmerimplementieren tatsächlich die suboptimale Tril-Division; Die Asymptotyken verschlechtern sich auf etwa n ^ 2 (oder sogar darüber), wenn Sie versuchen, noch mehr Primzahlen zu erzeugen.
Will Ness