Hallo Zusammen,

nach langer, langer Zeit habe ich mich endlich mal wieder am Programmieren versucht und daher das Sieb des Eratosthenes einmal programmiert.
Für mich sieht der Code (bin Anfänger / Amateur) recht schlank aus. Seht ihr noch Möglichkeiten die Performance zu steigern? Vor allem bei Zahlenbreiche von 50k+ dauert es doch schon recht lange. (Ja, mir sind die Rechendurchläufe mit den ganzen Schleifen schon bewusst und was sich da alles quadriert usw. ;-) )

using System;
using System.Windows.Forms;

namespace Primzahlberechnung
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            ulong end = Convert.ToUInt64(textBox1.Text);
            ulong[] primzahl = new ulong[end];

            // Füllen des Arrays mit allen Zahlen
            for (ulong i = 1; i < end; i++) 
            {
                primzahl[i] = i + 1;
            }
            for(ulong u = 2 ; u < end ; u++)
            {
                for (ulong zahl = 0; zahl ≤ Convert.ToUInt64(primzahl.Length)-1; zahl++)
                {
                    if (zahl ≥ 1)
                    {
                        if (primzahl[zahl] != u && primzahl[zahl] !=0) 
                        {
                            if (primzahl[zahl] % u == 0)
                            {
                                primzahl[zahl] = 0;
                            }
                        }
                    }
                }
            }

            // Ausgabe an die Listbox
            for(ulong zahl =0; zahl ≤ Convert.ToUInt64(primzahl.Length) - 1; zahl++)
            {
                if (primzahl[zahl] != 0)
                {
                    listBox1.Items.Add(primzahl[zahl].ToString());
                }
            }
        }
    }
}

Du beginnst mit zahl bei 0, wirst aber nur aktiv wenn zahl ≥ 1 :-)
Sofern das nicht sowieso raus optimiert wird, sparst du dir schon mal einen Vergleich pro Durchlauf, wenn du direkt bei 1 beginnst. Und du sparst dir optisch eine Einrückungsebene.

ConvertToInt64 brauchst du auch nicht, liest sich nur schwer aber der Compiler wandelt dir das automatisch um.

Was ich mir jetzt alles überlege, bitte selber noch nachprüfen.

Was genau soll in primzahl stehen? So wie ich das Sieb verstehe, markiert es Zahlen. Wäre also ein Array von bool Werten statt Zahlen?
Ich würde primzahl[ i ] nicht mit i+1 füllen, sondern mit i. Sonst kennt sich keiner mehr aus.
Das führt dann dazu dass du nicht mehr primzahl[zahl] auslesen musst was einen Zugriff auf das Array bedeutet, sondern du bei der Prüfung auf != u und der Rechnung mit % direkt zahl verwenden kannst.
Nur für primzahl [zahl] != 0 brauchst du noch das Array, denn das prüft die Markierung der Zahl, statt den Wert selbst.

Zu if (primzahl[zahl] % u == 0) was mit sinnvolleren Zuweisungen das selbe ist wie if (zahl % u == 0).
Die % Rechnung wird nicht Null, wenn zahl < u. Du kannst also die innere Schleife bei u beginnen, statt bei 0. Das spart einiges an Durchläufen.
Wenn du die Schleife erst bei u+1 beginnst und den Fall zahl == u separat in der äußeren Schleife behandelst, kannst du den Test primzahl[zahl] != u auch weglassen.0

Ein weiterer Ansatz: Das Sieb markiert Vielfache einer Zahl.
Du durchläufst JEDE Zahl und prüfst mit % ob sie ein Vielfaches von u ist. Das funktioniert zwar, ist aber sehr viel Aufwand. Für u = 1000 findest du ein Vielfaches und prüfst dann die nächsten 999 Zahlen ebenfalls, obwohl die kein Vielfaches sein können. Für u = 10000 prüfst du 9999 andere Zahlen ohne Ergebnis.
Also beginne die innere Schleife bei zahl = u und dann nicht mehr zahl++ sondern zahl += u. Dann brauchst du die % Operation nicht mehr und kannst ohne weitere Prüfung primzahl[zahl] = 0 setzen.

Hallo,

als erstes hättest du doch in die Wiki schauen können: Sieb des Eratosthenes
Und wie bei jeder Primzahlberechnung braucht man nur die Zahlen bis sqrt(N) testen (die größeren Zahlen bis N wurden schon durch die Markierungsschleifen vorher durchlaufen).

Danach könntest du dich am Sieb von Atkin versuchen.

PS: Auch als Anfänger solltest du gleich von Beginn an Logik und UI voneinander trennen, d.h. die Primzahlberechnung zumindestens in einer eigenen Methode (am besten aber gleich in einer eigenen Klasse) durchführen.

https://www.youtube.com/watch?v=pv4Yq35Chx0
Dave Plummer hat gerade eine Serie wo er die Performance von 45 Sprachen vergleicht, u.a. auch C#
https://github.com/PlummersSoftwareLLC/Primes
Das sollte wohl die schnellste Möglichkeit in C# sein.

Hallo und danke für die ganzen Vorschläge und Hinweise auf Fehler ;-)

Dann werde ich mir das doch heute Abend einmal mit einem Timer versehen und mal Laufzeittests machen.