[C#] Sieb des Eratosthenes optimieren

tortelini66

Redshirt
★ Themenstarter ★
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
 

vibeseeker

Vice Admiral Special
Mitglied seit
21.01.2008
Beiträge
699
Renomée
66
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.
 

BoMbY

Grand Admiral Special
Mitglied seit
22.11.2001
Beiträge
7.468
Renomée
293
Standort
Aachen
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.
 

vibeseeker

Vice Admiral Special
Mitglied seit
21.01.2008
Beiträge
699
Renomée
66
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:

Antarctica

Grand Admiral Special
Mitglied seit
11.09.2004
Beiträge
2.445
Renomée
34
Standort
Kupferstadt Stolberg
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 :)
 

vibeseeker

Vice Admiral Special
Mitglied seit
21.01.2008
Beiträge
699
Renomée
66
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.
 

BoMbY

Grand Admiral Special
Mitglied seit
22.11.2001
Beiträge
7.468
Renomée
293
Standort
Aachen
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 ...
 

PuckPoltergeist

Grand Admiral Special
Mitglied seit
18.01.2002
Beiträge
16.734
Renomée
145
Standort
Ilmenau
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:

vibeseeker

Vice Admiral Special
Mitglied seit
21.01.2008
Beiträge
699
Renomée
66
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:

PuckPoltergeist

Grand Admiral Special
Mitglied seit
18.01.2002
Beiträge
16.734
Renomée
145
Standort
Ilmenau
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.
 
Oben Unten