Samstag, 26. Juni 2010

Primzahlen ausgeben mit dem Sieb des Eratosthenes

Heute möchte ich euch eine C# - Implementierung eines Algorithmus' zeigen, der alle Primzahlen von 2 bis zu einer oberen Grenze ausgibt.
Da der Name des Algorithmus durch den griechischen Mathematiker Eratosthenes von Kyrene geprägt wurde, nennt man diesen das "Sieb des Eratosthenes".
In allgemeiner Sprechweise funktioniert das Sieb folgendermaßen wobei N die Obergrenze sei:
Man schreibt alle Zahlen von 2 - N auf. Die kleinste nicht durchgestrichene Zahl ist immer eine Primzahl. Anfangs ist das die 2. Ausgehend von der kleinsten nicht durchgestrichenen Zahl werden dann alle Vielfachen dieser durchgestrichen, wobei es genügt, wenn man mit der Quadratzahl der Zahl beginnt.
Alle am Ende übrig gebliebenen, nicht durchgestrichenen Zahlen sind Primzahlen.
Jetzt die Implementierung als C# - Konsolenanwendung:

    class SiebDesEratosthenes
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Geben Sie die obere Grenze ein:");
            int UpperBound = int.Parse(Console.ReadLine()); // Zahl, bis zu der gesucht werden soll, eingeben
            bool[] Tagged = new bool[UpperBound + 1]; // Array zur Speicherung, ob die zum Index passende Zahl gestrichen wurde

            // Array mit false initialisieren
            for (int i = 0; i < Tagged.Length; i++)
                Tagged[i] = false;

            // alle Zahlen bis zur Wurzel der oberen Zahl durchlaufen
            for (int i = 2; i < Math.Ceiling(Math.Sqrt(UpperBound)); i++)
            {
                if (!Tagged[i])
                {
                    int j = i;
                    // alle Vielfachen der Zahl i, angefangen von ihrer Quadratzahl, durchstreichen
                    while (j * i <= UpperBound)
                    {
                        Tagged[j * i] = true;
                        j++;
                    }
                }
            }

            // alle nicht durchgestrichenen Zahlen ausgeben
            for (int i = 2; i < Tagged.Length; i++)
            {
                if (!Tagged[i])
                    Console.Write(i.ToString() + " ");
            }
        }
    }

Kommentare:

  1. So gehts richtig :P

    static void Main(string[] args)
    {
    Console.WriteLine("Geben Sie die obere Grenze ein:");
    int UpperBound = int.Parse(Console.ReadLine()); // Zahl, bis zu der gesucht werden soll, eingeben
    bool[] Tagged = new bool[UpperBound+1]; // Array zur Speicherung, ob die zum Index passende Zahl gestrichen wurde

    // Array mit false initialisieren
    for (int i = 0; i < Tagged.Length; i++)
    Tagged[i] = false;

    // alle Zahlen bis zur Wurzel der oberen Zahl durchlaufen
    for (int i = 2; i <= Math.Ceiling(Math.Sqrt(UpperBound)); i++)
    {
    if (!Tagged[i])
    {
    int j = i;
    // alle Vielfachen der Zahl i, angefangen von ihrer Quadratzahl, durchstreichen
    Hier ist der Fehler:
    while (j * i <= UpperBound)
    {
    Tagged[j * i] = true;
    j++;
    }
    }
    }

    // alle nicht durchgestrichenen Zahlen ausgeben
    for (int i = 2; i < Tagged.Length; i++)
    {
    if (!Tagged[i])
    Console.Write(i.ToString() + " ");
    }

    Console.ReadLine();
    }

    AntwortenLöschen
  2. public static ArrayList Prim(int Max) {

    // Werden automatisch mit false vorbelegt
    bool[] Gestrichen = new bool[Max + 1];

    // Startwert
    int Start = 2;

    // Wurzel
    int tmpMax = (int)Math.Sqrt(Max);

    for (int i = Start; i < tmpMax; i++) {

    for (int j = i + i; j < Max; j += i) {
    // Keine Primzahlen markieren!
    Gestrichen[j] = true;
    }

    // Optimierung
    for (; Gestrichen[i + 1] == true; i++) { }

    }

    ArrayList Prim = new ArrayList();


    for (int i = Start; i < Max; i++) {

    if (Gestrichen[i] == false) {
    // Primzahlen sammeln
    Prim.Add(i);
    }

    }

    return Prim;
    }

    AntwortenLöschen
  3. und wie schreibt man code, wenn alle primzahlen durchlaufen sollen, bis der anwender der konsole stop drückt?

    AntwortenLöschen
    Antworten
    1. Das würde ich in einer Windows Forms Anwendung machen. Einen Button einfügen, bei Klick setzt dieser eine Variable X auf true. Dann den obigen Siebcode in eine Schleife mit while(X == false) { ... }, und in der Schleife Application.DoEvents() aufrufen damit die Anwendung bedienbar bleibt.

      Löschen