[C#] Sieb des Eratosthenes optimieren

tortelini66

Redshirt
Mitglied seit
14.01.2014
Beiträge
1
Renomée
0
Hallo zusammen,
ich bin hier auf einen Thread von 2005 gestoßen, der sich mit dem Finden eines schnellen Primzahlalgorithmus beschäftigt hat. Die Ergebnisse die dort zustande gekommen sind haben mich zum staunen gebracht, nur leider habe ich das Meiste nicht verstanden.
Ich arbeite zurzeit selbst spaßeshalber an einer Implementierung des Siebes von Eratosthenes in C# und komme Singlethreaded mittlerweile auf eine Zeit von 9,8 Sekunden auf einem Intel Xeon-e3 1230v3 @3300MHz für alle Primzahlen bis eine Milliarde. Gerne würde ich das noch weiter optimieren. Vielleicht kann mir da ja jemand helfen.

Hier erstmal der Code:
Code:
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Collections;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int maximum;
            Console.Write("Grenze: ");
            maximum = Int32.Parse(Console.ReadLine());

            Calculate(maximum);

            Console.ReadKey();
        }
        static void Calculate(int border)
        {
            BitArray sieb = new BitArray(border, false);
            int i = 3;
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            while (i * i < border)
            {
                if (!sieb[i])
                {
                    for (int j = i * i; j < border; j += 2*i)
                    {
                        sieb[j] = true;
                    }
                }
                i += 2;
            }
            stopWatch.Stop();
            int counter = 0;
            for (i = 3; i < border; i+=2)
            {
                if (!sieb[i])
                {
                    counter++;
                }
            }
            counter++;
            Console.WriteLine(counter + " Primzahlen in " + stopWatch.ElapsedMilliseconds + " ms gefunden"); //Ausgabe der Anzahl gefundener Primzahlen zur Überprüfung der Richtigkeit inklusive gebrauchter Zeit
        }
    }
}

Über Anregungen und Vorschläge zur Verbesserung würde ich mich sehr freuen.

Gruß
Tobi
 
Hallo,

du kannst noch ein bisschen was rausholen, wenn du in der while-Schleife nicht in jeder Iteration i quadrierst, sondern vor der Schleife einmal die Wurzel von border berechnest und dann i < sqrt(border) als Bedingung nimmst. Ich konnte damit in Java knapp 10% rausholen (~5600 statt ~6200 ms).

Ansonsten musst du wohl einen besseren Algorithmus benutzen.
 
Ansonsten musst du wohl einen besseren Algorithmus benutzen.

Ich zitiere mal kurz die Wikipedia: Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes. Bis heute ist kein effizienter Primzahlgenerator bekannt.

Die Implementierung davon ist allerdings eine andere Sache. Das kann man bestimmt noch was optimieren - prinzipiell müsste man das zum Beispiel parallelisieren können, mit OpenCL und HSA zum Beispiel.
 
Ich zitiere mal kurz die Wikipedia: Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes. Bis heute ist kein effizienter Primzahlgenerator bekannt.

Die Implementierung davon ist allerdings eine andere Sache. Das kann man bestimmt noch was optimieren - prinzipiell müsste man das zum Beispiel parallelisieren können, mit OpenCL und HSA zum Beispiel.

Kannst du den Artikel verlinken, in dem das steht? Ich bin da anderer Meinung und Wikipedia gibt mir auch Recht (wobei wir beide wissen, dass Wikipedia die mitunter schlechteste Quelle ist). Zuerstmal, dass es ein schnelleres Verfahren als das von Eratosthenes gibt:

https://de.wikipedia.org/wiki/Primzahltest#Sieb_von_Atkin
Das Sieb von Atkin ist ein schneller, moderner Algorithmus zur Bestimmung aller Primzahlen bis zu einer vorgegebenen Grenze. Es ist eine optimierte Version des antiken Sieb des Eratosthenes. Die Performance ist bei einem kleinen Limit von z.B. 100 noch etwas langsamer als bei dem Sieb des Eratosthenes, aber je größer das Limit, desto größer ist der Zeitvorteil gegenüber der alten Siebmethode.

Außerdem hat der Sieb des Eratosthenes exponentielle (genauer: pseudopolynomielle) Laufzeit, seit 2002 hingegen existiert ein Verfahren, das Primzahlen in polynomieller Laufzeit berechnet.

Edit: Ob der AKS-Algorithmus in der Praxis tatsächlich schneller ist, bzw. bis zu welcher Zahl, steht natürlich auf einem anderen Blatt. Hier hat sich jemand mit AKS und Rabin-Miller beschäftigt.
 
Zuletzt bearbeitet:
Wikipedia hat Recht, bitte fangt doch mal an zu lesen.

"Bis heute ist kein effizienter Primzahlgenerator bekannt" ist korrekt.

"Bis heute ist kein effizienterer Primzahlgenerator bekannt" wäre nicht korrekt.

Der kleine aber feine Unterschied zwischen Positiv und Komparativ :)
 
Wikipedia hat Recht, bitte fangt doch mal an zu lesen.

"Bis heute ist kein effizienter Primzahlgenerator bekannt" ist korrekt.

"Bis heute ist kein effizienterer Primzahlgenerator bekannt" wäre nicht korrekt.

Der kleine aber feine Unterschied zwischen Positiv und Komparativ :)

Das habe ich echt überlesen. Trotzdem halte ich es für falsch, da mit dem AKS-Algorithmus ja ein effizienter Algorithmus zur Verfügung steht.
 
AKS ist doch nur ein Primzahlentest? Und das Atkin-Sieb ist nur eine optimierte Variante von Eratosthenes. Das Sieb liefert sicher alle Primzahlen, und hat gerade den Vorteil, dass man nicht auf Prim prüfen muss ...
 
AKS ist doch nur ein Primzahlentest? Und das Atkin-Sieb ist nur eine optimierte Variante von Eratosthenes. Das Sieb liefert sicher alle Primzahlen, und hat gerade den Vorteil, dass man nicht auf Prim prüfen muss ...

Zum einen das, zum anderen kommt es darauf an, was man unter effizient versteht. Macht man es sich einfach und beschränkt sich z.B. auf die Primzahlen im bereich 1-1000, so kann man sich das bei heutiger Hardware mit dem grottigsten Algorithmus schön färben. Betrachtet man es aus der Komplexitätstheorie, gibt es jedoch keinen effizienten Algorithmus. Nicht zuletzt darauf baut immer noch RSA mit auf. Die Zahlen müssen nur groß genug werden, und jeder bekannte Algorithmus bricht dabei ein.

Ach ja, und nur weil ein Algorithmus Polynomiallaufzeit hat, muss er noch lange nicht effizient sein. Je nach Vorgehen kann für kleine Zahlen ein Algorithmus mit exponentieller Laufzeit sogar schneller sein.
 
Zuletzt bearbeitet:
Zum einen das, zum anderen kommt es darauf an, was man unter effizient versteht. Macht man es sich einfach und beschränkt sich z.B. auf die Primzahlen im bereich 1-1000, so kann man sich das bei heutiger Hardware mit dem grottigsten Algorithmus schön färben. Betrachtet man es aus der Komplexitätstheorie, gibt es jedoch keinen effizienten Algorithmus. Nicht zuletzt darauf baut immer noch RSA mit auf. Die Zahlen müssen nur groß genug werden, und jeder bekannte Algorithmus bricht dabei ein.

Da liegst du falsch, das Primzahlproblem ("ist Zahl n Primzahl?") liegt in P und ist damit effizient berechenbar, wenn man effizient im Sinne der Komplexitätslehre betrachtet (in polynomieller Zeit lösbar). Das andere ist das Faktorisierungsproblem; dieses ist NP-vollständig und damit nicht effizient lösbar. Davon lebt die Kryptographie.

Edit: Es ist offenbar nicht bewiesen, dass das Faktorisierungsproblem NP-vollständig ist, es ist allerdings kein effizienter Algorithmus bekannt.

Ach ja, und nur weil ein Algorithmus Polynomiallaufzeit hat, muss er noch lange nicht effizient sein. Je nach Vorgehen kann für kleine Zahlen ein Algorithmus mit exponentieller Laufzeit sogar schneller sein.

Da hast du allerdings Recht :) Wenn ich effizient sage, meine ich (zumindest in diesem Kontext) schon "von deterministischer TM in polynomieller Zeit lösbar". Ab einer bestimmten Eingabegröße hängt jedoch jeder effiziente Algorithmus einen anderen mit exponentieller Laufzeit ab.
 
Zuletzt bearbeitet:
Da liegst du falsch, das Primzahlproblem ("ist Zahl n Primzahl?") liegt in P und ist damit effizient berechenbar, wenn man effizient im Sinne der Komplexitätslehre betrachtet (in polynomieller Zeit lösbar).
Nein, du drehst hier eine Aussage um. Die Aussage ist, liegt ein Problem in NP, so gibt es (nach aktuellem Stand der Dinge) keinen effizienten Algorithmus, der das Problem löst. Das kann man aber nicht umdrehen. Nur weil ein Problem in P liegt, muss dafür nicht automatisch ein effizienter Algorithmus existieren. Auch nicht im Sinne der Komplexitätslehre. Das Polynom muss nur groß genug werden, um den Algorithmus ineffizient sein zu lassen.

Deshalb spielt AKS in der Praxis auch überhaupt keine Rolle. Er ist theoretisch sehr interessant, weil eben damit der Beweis erbracht wurde, dass der Test auf prim in P liegt. Praktisch kommt aber Miller-Rabin eine weitaus größere Bedeutung zu.
 
Zurück
Oben Unten