Entwickler-Ecke :: Thema anzeigen - [C#] erathosthenes algorithmus

sepp_a_u - Mo 01.10.07 21:45
Titel: [C#] erathosthenes algorithmus

hi @ all

bin anfänger in c# und wollte mal meinen ersten algorithmus vorstellen:

das sieb des eratosthenes:
hier mal der code. vll kann man daran ja noch was verbessern?

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            long max;
            Console.Write("Bitte geben Sie eine Grenze ein: ");
            max = Int32.Parse(Console.ReadLine());

            Primzahlen(max);

            Console.WriteLine("\n\nPress ENTER to leave");
            Console.ReadLine();
        }
        static void Primzahlen(long grenze)
        {
            int i;
            bool[] sieb = new bool[grenze + 1];
            for (i = 2; i <= grenze; i++)
            {
                sieb[i] = false;
            }
            i = 2;
            while (i * i <= grenze)
            {
                if (!sieb[i])
                {
                    for (int j = i * i; j <= grenze; j = j + i)
                    {
                        sieb[j] = true;
                    }
                }
                i++;
            }
            for (i = 2; i <= grenze; i++)
            {
                if (!sieb[i])
                {
                    Console.Write(i + " ");
                }
            }
        }
    }
}

mfg

r2c2 - Di 02.10.07 08:51
Titel: Re: [C#] erathosthenes algorithmus

Hallo,

meine Kommentare zum Code:

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            long max;
            Console.Write("Bitte geben Sie eine Grenze ein: ");
            max = Int32.Parse(Console.ReadLine()); // was machst du, wenn der User gar keine Zahl eingibt, sondern z.B. "Hallo"

            Primzahlen(max);

            Console.WriteLine("\n\nPress ENTER to leave"); // Wasw jetzt nun? Deutsch oder Englisch?
            Console.ReadLine();
        }
        static void Primzahlen(long grenze) // Funktionen benennt man normalerweise nach Verben. Also nicht Primzahlen, sondern: FindeFrimzahlen oder sowas...
        {
            int i;
            bool[] sieb = new bool[grenze + 1];
            for (i = 2; i <= grenze; i++)
            {
                sieb[i] = false;
            }
            i = 2;
            while (i * i <= grenze) // kann man so amchen, ja. 
// Geht aber besser: So wird pro Schleifendurchlauf einmal multipliziert. 
// Besser man zieht ganz zu Anfang einmal die Wurzel und prüft auf i <= wurzel. 
// Nun ich die Wurzelfunktion auch nicht sonderlich schnell, und bis auch die 20.
// Nachkommastelle brauchst dus auch nicht. Also wäre zu überlegen, ob man ne 
// eigene Wurzelfunktion schreibt, die nach einer Nachkommastelle abbricht... 
// ==> siehe z.B. Heron-Algorithmus
            {
                if (!sieb[i])
                {
                    for (int j = i * i; j <= grenze; j = j + i) // so, jetzt wirds ganz merkrürdig:
// was machst du hier? Das ist aber nicht der korrekte Algorithmus 
// und ich zweifle hochgradig, dass das so funktuioniert.
// Beispiel: i = 2, grenze = 10
// i*i = 4 ==> du setzt alles von 4 bis einschließlich 10 auf true. 
// 4,6,8,9 und 10 sind aber definitiv keine Primzahlen...
                    {
                        sieb[j] = true;
                    }
                }
                i++;
            }
            for (i = 2; i <= grenze; i++)
            {
                if (!sieb[i])
                {
                    Console.Write(i + " ");
                }
            }
        }
    }
}

mfg

Christian

Horst_H - Di 02.10.07 09:21

Hallo,

der Algorithmus stimmt schon, denn die Ausgabe bezieht sich auf !sieb[i]
Es wäre einleuchtender das Feld auf true zu setzen und anschliessend alle nicht Primzahlen auf false.

C#-Quelltext

1:
2:
3:
4:

 if (!sieb[i]) 
                { 
                    Console.Write(i + " "); 
                }

Gruß Horst

Kha - Di 02.10.07 10:52

Für einen Anfänger ist die Umsetzung wirklich gut gelungen, hier noch ein paar Tipps:
Das Array ist schon mit false initialisiert, die erste Schleife kann also weggelassen werden. Die letzte lässt sich ebenfalls entfernen, indem sie in die mittlere integriert wird. Außerdem sollte der Algorithmus allgemein einsetzbar gemacht werden, indem er IEnumerable<int> zurückgibt.

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

using System;
using System.Collections.Generic;

static class SieveOfEratosthenes
{
  public static IEnumerable<int> FindPrimes(int limit) // was eigentlich nun, long oder int ;) ?
  {
    // zu überlegen wäre der Einsatz eines BitArrays,
    // ist wie immer eine Entscheidung zwischen Performance und Speicherverbrauch
    bool[] sieve = new bool[limit + 1];
    int limitSqrt = (int)Math.Sqrt(limit);

    for (int i = 2; i <= limit; i++)
      if (!sieve[i]) {
        yield return i;
        if (i <= limitSqrt)
          for (int j = i * i; j <= limit; j += i)
            sieve[j] = true;
      }
  }
}

Viel mehr zu optimieren würde ich gar nicht versuchen, dafür nimmt man einfach einen besseren Algo ;) .

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!