Primzahlenprüfer

Endlich habe ich doch geschafft mich mit .Net 2.0 und C# etwas näher beschäftigen zu können. Beruflich habe ich mit im Bereich von ASP.Net und Visual Basic.Net schon etwas ausgetobt und meine ersten Erfahrungen gesammelt. Nebenbei muß ich sagen, das die serverseitige Programmierung mit ASP.Net wirklich super ist, aber darum geht es hier nicht.

Ich habe mir doch mal etwas Zeit genommen, um mich mit den Konzepten von C# etwas genauer zu beschäftigen. Als Beispiel habe ich mit einen Primzahlenprüfer ausgedacht. Gut - Primzahlen zu prüfen ist nicht schwer, aber zum ausprobieren ganz gut. Ziel war es ein Programm zu schreiben, mit dem man verschiedene Methoden implementieren kann, um eine Primzahl zu testen. Welche Methoden es gibt könnt ihr hier bei Wikipedia nachlesen. Einige Primzahlen könnt ihr hier nachlesen.

Hauptsächlich wollte ich mich mit dem Thema Schnittstellen in C# beschäftigen und eine Primzahlenprüfung fand ich da ziemlich passen.

Der Grundalgorithmus war ziemlich einfach:

bool PrimTest(ulong n) {
    bool isteilbar = false;

    //bekannte Primfaktoren testen
    foreach (ulong primfaktor in Primzahlen) {
        if (n % primfaktor == 0) {
            isteilbar = true;
            break;
        }
    }

    if (!isteilbar) {
        ulong i = Primzahlen[Primzahlen.Count - 1] + 2;
        bool isTeilbarSub = false;
        while (i <= n) {
            isTeilbarSub = false;
            foreach (ulong primfaktor in Primzahlen) {
                bool isTeiler = (i % primfaktor == 0);
                if (isTeiler) {
                    isTeilbarSub = true;
                    break;
                }
            }
            if (!isTeilbarSub) {
                Primzahlen.Add(i);
            }

            i = i + 2;

        }
        isteilbar = isTeilbarSub;
    }
    return (!isteilbar);
}

Eigentlich wollte ich noch einen Test einbauen, aber diesen habe ich weggelassen, da die aussage im Rechner nicht hinreichend gesichert ist. Den jede Zahl von der sich ganzzahlig eine Wurzel ziehen läßt ist mit Sicherheit keine Primzahl. Leider ist die Wurzel nur eine Näherung und deshalb kann man sich nicht so genau drauf verlassen. Wer aber Lust kann mir gern eine Ergänzung schicken ... ;-)

Okay so weit so gut ... aber was hat das mit Schnittstellen zu tun ... ganz einfach ... in C# bzw. .Net gibt die Möglichkeit eine Schnittstelle zu implementieren. Für die Primzahlenprüfung habe ich folgende Schnittstelle gewählt.

interface IPrimzahlPruefer
{
    bool IsPrimzahl(ulong n, out ulong Primfaktor );
    List PrimZahlen {get; set;}
}

    

Hier noch eine andere Art der Implementierung des Interfaces und zwar nach dem "Sieb des Eratosthenes". Es ist ein recht schnelles Verfahren, es füllt ein Array oder wie in diesem Fall eine List mit der gesamtheit aller Zahlen bis zu einer Grenze gefüllt ( 2,3,4,5 ... n ). Dann wird beim ersten Element angefangen und die Vielfachen dieser Zahl aus dem Index entfernt. Was mit der Generic-Liste von .Net unter C# ziemlich einfach umzusetzten ist.

Wurden alle Vielfachen entfernt, geht es zum nächsten Element und das selbe nochmal, das was übrig bleibt ist eine Liste von Primzahlen und das geht schneller als mit dem oberen Algorythmus. Schaut es euch an:

   
    class PrimzahlPrueferEratosthenesSieb : IPrimzahlPruefer
    {

        List primZahlenList;
        ulong faktor;
        ulong index;

        public PrimzahlPrueferEratosthenesSieb()
        {
            primZahlenList = new List();
        }

        void FillList(ulong n)
        {
            primZahlenList.Clear();
            for (ulong i = 2; i <= n; i++)
            {
                primZahlenList.Add(i);
            }

        }
        private void CheckList()
        {
            int i = 0;
            while (i < primZahlenList.Count)
            {
                faktor = primZahlenList[i];
                primZahlenList.RemoveAll(RemoveZahl);

                i++;
            }
        }

        private bool RemoveZahl(ulong zahl)
        {
            bool rc = false;
            if (zahl > faktor)
            {
                rc = (zahl % faktor == 0);
            }
            return rc;
        }

        #region IPrimzahlPruefer Members

        public bool IsPrimzahl(ulong n, out ulong Primfaktor)
        {
            FillList(n);
            CheckList();
            
            Primfaktor = 1;
            return (primZahlenList.Contains(n));
        }


        public List PrimZahlen
        {
            get
            {
                return primZahlenList;
            }
            set
            {
                if (primZahlenList != value)
                {
                    primZahlenList = value;
                }
            }
        }

        #endregion
    }
    

Eine andere Art coole Primzahlen zu prüfen gibt es hier

copyright wilderland