App installieren
How to install the app on iOS
Follow along with the video below to see how to install our site as a web app on your home screen.
Anmerkung: This feature may not be available in some browsers.
Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden.
Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
[C#] Sieb des Eratosthenes optimieren
- Ersteller tortelini66
- Erstellt am
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:
Über Anregungen und Vorschläge zur Verbesserung würde ich mich sehr freuen.
Gruß
Tobi
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.
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
- Prozessor
- Ryzen 3700X
- Mainboard
- Gigabyte X570 Aorus Elite
- Kühlung
- Noctua NH-U12A
- Speicher
- 2x16 GB, G.Skill F4-3200C14D-32GVK @ 3600 16-16-16-32-48-1T
- Grafikprozessor
- RX 5700 XTX
- Display
- Samsung CHG70, 32", 2560x1440@144Hz, FreeSync2
- SSD
- AORUS NVMe Gen4 SSD 2TB, Samsung 960 EVO 1TB, Samsung 840 EVO 1TB, Samsung 850 EVO 512GB
- Optisches Laufwerk
- Sony BD-5300S-0B (eSATA)
- Gehäuse
- Phanteks Evolv ATX
- Netzteil
- Enermax Platimax D.F. 750W
- Betriebssystem
- Windows 10
- Webbrowser
- Firefox
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.444
- Renomée
- 34
- Standort
- Kupferstadt Stolberg
- Mein Laptop
- HP 625, V140, 4GB RAM, 32GB SSD, Ubuntu 15.04 (WT279EA)
- Prozessor
- Intel Core i5-4690, 4x 3.50GHz, boxed (BX80646I54690)
- Mainboard
- ASRock H97M Pro4 (90-MXGTA0-A0UAYZ)
- Kühlung
- Scythe Big Shuriken 2 Rev. B (SCBSK-2100)
- Speicher
- 2x Exceleram Black and White 8GB PC3-12800 DDR3-1600 Kit (EBW301A)
- Grafikprozessor
- Gigabyte GeForce GTX 750 Ti OC low profile, 2GB GDDR5, DVI, 2x HDMI, DisplayPort (GV-N75TOC-2GL)
- Display
- Samsung SyncMaster T24A350, 24" (LT24A350EW)
- SSD
- Samsung SSD 960 EVO 500GB, PCIe (MZ-V6E500BW)
- HDD
- 2x Seagate GoFlex Desk 3TB, USB 3.0 (STAC3000201/STAC3000202)
- Optisches Laufwerk
- Samsung SH-224BB schwarz, SATA, retail (SH-224BB/RSMS)
- Soundkarte
- on-board
- Gehäuse
- Inter-Tech IT-5908
- Netzteil
- be quiet! System Power S6 80Plus 300W ATX 2.2 (S6-SYS-UA-300W/BN080)
- Betriebssystem
- Microsoft: Windows 10 Pro 64Bit, DSP/SB (deutsch) (PC) (FQC-08922)
- Webbrowser
- Mozilla Firefox
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
"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
- Prozessor
- Ryzen 3700X
- Mainboard
- Gigabyte X570 Aorus Elite
- Kühlung
- Noctua NH-U12A
- Speicher
- 2x16 GB, G.Skill F4-3200C14D-32GVK @ 3600 16-16-16-32-48-1T
- Grafikprozessor
- RX 5700 XTX
- Display
- Samsung CHG70, 32", 2560x1440@144Hz, FreeSync2
- SSD
- AORUS NVMe Gen4 SSD 2TB, Samsung 960 EVO 1TB, Samsung 840 EVO 1TB, Samsung 850 EVO 512GB
- Optisches Laufwerk
- Sony BD-5300S-0B (eSATA)
- Gehäuse
- Phanteks Evolv ATX
- Netzteil
- Enermax Platimax D.F. 750W
- Betriebssystem
- Windows 10
- Webbrowser
- Firefox
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
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
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.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).
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.
Ähnliche Themen
- Antworten
- 27
- Aufrufe
- 4K
- Antworten
- 7
- Aufrufe
- 3K
- Antworten
- 1
- Aufrufe
- 2K