Sieb des Eratosthenes

  • Allgemein

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von faxe1008.

    Sieb des Eratosthenes

    Hi,

    Ich probiere gerade das Sieb des Eratosthenes in einer Konsole zu verwenden. Das funktioniert so:
    - Lösche die Vielfachen von 2,3,5,7,11
    - Suche ob Vielfache der übrigen Zahlen vorhanden sind und lösche

    Ich habe eine Variante davon geschrieben, allerdings habe ich das Problem, dass ich die Schleife updaten müsste, so dass nur noch die Zahlen durchgegangen werden müssen die übrig sind. Dies würde auch eine deutlich höhere Perfomance bringen.

    C#

    Brainfuck-Quellcode

    1. // Start einlesen
    2. Console.WriteLine("Untergrenze:");
    3. int untergrenze = int.Parse(Console.ReadLine());
    5. // Ende einlesen
    6. Console.WriteLine("Obergrenze:");
    7. int obergrenze = int.Parse(Console.ReadLine());
    9. // Zahlenliste befüllen
    10. IList<int> zahlenliste = new List<int>();
    11. for (int u = untergrenze; u <= obergrenze; u++)
    12. {
    13. zahlenliste.Add(u);
    14. }
    15. Console.WriteLine("--------------------------------------------");
    19. // Filtern
    20. for(int i = 2; i <= zahlenliste.Count - 1; i++)
    21. {
    22. for (int z = 0; z <= zahlenliste.Count - 1; z++)
    23. {
    25. if (zahlenliste.ElementAt(z) % i == 0)
    26. {
    27. if (zahlenliste.ElementAt(z) != i) { zahlenliste.RemoveAt(z); }
    28. }
    29. }
    30. }
    33. for (int w = 0; w <= zahlenliste.Count - 1; w++)
    34. {
    35. Console.WriteLine(zahlenliste.ElementAt(w).ToString());
    36. }
    39. Console.ReadKey();
    40. Console.Clear();


    VB.NET

    VB.NET-Quellcode

    1. ' Start einlesen
    2. Console.WriteLine("Untergrenze:")
    3. Dim untergrenze As Integer = Integer.Parse(Console.ReadLine())
    5. ' Ende einlesen
    6. Console.WriteLine("Obergrenze:")
    7. Dim obergrenze As Integer = Integer.Parse(Console.ReadLine())
    9. ' Zahlenliste befüllen
    10. Dim zahlenliste As IList(Of Integer) = New List(Of Integer)()
    11. For u As Integer = untergrenze To obergrenze
    12. zahlenliste.Add(u)
    13. Next
    14. Console.WriteLine("--------------------------------------------")
    18. ' Filtern
    19. For i As Integer = 2 To zahlenliste.Count - 1
    20. For z As Integer = 0 To zahlenliste.Count - 1
    22. If zahlenliste.ElementAt(z) Mod i = 0 Then
    23. If zahlenliste.ElementAt(z) <> i Then
    24. zahlenliste.RemoveAt(z)
    25. End If
    26. End If
    27. Next
    28. Next
    31. For w As Integer = 0 To zahlenliste.Count - 1
    32. Console.WriteLine(zahlenliste.ElementAt(w).ToString())
    33. Next
    36. Console.ReadKey()
    37. Console.Clear()

    8-) faxe1008 8-)

    Also ich habs mal probiert aber keine Ahnung ob das schnell ist:

    VB.NET-Quellcode

    1. Module Module1
    2. Sub Main()
    3. Do
    4. Console.WriteLine("Zahl eingeben: ")
    5. Dim parse As Integer
    6. Integer.TryParse(Console.ReadLine(), parse)
    7. Console.WriteLine("")
    8. Console.WriteLine("Endzahl eingeben: ")
    9. Dim endzahl As Integer
    10. Integer.TryParse(Console.ReadLine(), endzahl)
    11. Console.WriteLine("")
    12. Console.WriteLine("Primzahlen: ")
    13. For x = parse To endzahl
    14. If x = 2 OrElse x = 3 OrElse x = 5 OrElse x = 7 OrElse x = 11 OrElse ModNull(2, x) AndAlso ModNull(3, x) AndAlso ModNull(5, x) AndAlso ModNull(7, x) AndAlso ModNull(11, x) Then
    15. Console.WriteLine(x)
    16. End If
    17. Next
    18. Loop
    19. Console.ReadLine()
    20. End Sub
    21. Private Function ModNull(ByVal Zahl As Integer, ByVal Schleifenzahl As Integer) As Boolean
    22. Return Math.IEEERemainder(Schleifenzahl, Zahl) <> 0
    23. End Function
    24. End Module

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()

    Ich seh zwar keine Frage, aber hier ein paar Kritik-/Anregungspunkte:
    a) Beim Sieb des Eratosthenes brauchst du keine Untergrenze, da die Untergrenze IMMER 2 ist.
    b) Warum machst du das so umständlich? Guck dir System.Linq.Enumerable.Range(int, int) an.
    c) Warum For-Schleifen? Linq tut es in dem Fall auch.
    Meine Quick-and-Dirty Lösung:
    coll.Where(item => !check.Any(inner => inner < item & item % inner == 0)),
    coll.Where(Function(item) Not check.Any(Function(inner) item > inner And item Mod inner = 0)).

    Erweitert.
    Copy&Paste-Schutz:

    @faxe1008:: Nicht die Elemente removen, das dauert unendlich lange.
    Trag in die betreffenden Felder eine 0 ein, und alle, die am Ende verschieden von 0 sind, sind Primzahlen.
    Das lässt sich mit Parallel.For herrlich parallelisieren.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Für diese Aufgabe halte ich die LINQ weder für eine schöne, noch für eine performante Lösung. Es ist einfach nur ein "weil man es kann und es cool aussieht".
    Meine Wahl würde ebenfalls auf @RodFromGermany:s Empfehlung fallen.

    Edit:
    Lol, die Version von AliveDevil benutzt ja nichtmal das Sieb des Eratosthenes. Das ist Primzahlenberechnung mit Modulo - ein ganz anderer Algorithmus (auch viel langsamer).
    Von meinem iPhone gesendet

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nikeee13“ ()

    Ich habe mir Parallel.For angesehen, aber das ist denke ich nicht die Lösung des Problems (nicht die Performance). Das Problem ist eher folgendes (Beispiel):



    1. Alle Zahlen die durch 1 teilbar sind rauswerfen => Macht ja keinen Sinn den jede ist durch 1 teilbar
    2. Alle Zahlen die durch 2 teilbar sind außer der 2 eliminieren:

    3. Nächste stehen gebliebene Zahl ist 3 => alle durch 3 teilbaren Zahlen eliminieren:

    4. Nächste stehen gebliebene Zahl ist 5 => alle durch 5 teilbaren Zahlen eliminieren:


    So das Problem, dass sich hierbei stellt ist, dass die For-Schleife weiterspringen müsste wenn sie zum Beispiel gerade 3 eliminiert hat muss sie ja nicht zu 4 weiterspringen, weil die 4 schon durch die 2 rausgeworfen wurde, sollte sie zur 5 weiter.

    Ich hoffe ich konnte es anschaulich erklären.

    8-) faxe1008 8-)

    Deshalb setzt du die Schrittweite der For-Schleife auch immer auf das, was eliminiert werden soll. Ist die Schleife bei 3, springt er als nächstes zu 6. Gerade das ist ja eine der Optimierungen vom Sieb.
    Von meinem iPhone gesendet

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nikeee13“ ()

    @nikeee13: Ok habe nur ein problem beim Implemetieren:
    1.) Schrittweite inkrementieren
    2.) Liste durchgehen und dann mit der Schrittweite Removen

    VB.NET-Quellcode

    1. int schrittweite = 0;
    5. for (int u = 0; u <= zahlenliste.Count - 1; u++)
    6. {
    7. schrittweite = u;
    8. for (int toremove = 0; toremove <= zahlenliste.Count - 1; toremove = schrittweite + toremove)
    9. {
    11. zahlenliste.RemoveAt(toremove);
    13. }
    15. }


    Das funktioniert leider nicht. Was passt hier nicht?

    8-) faxe1008 8-)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „faxe1008“ ()

    Besser wäre es, wenn du die rausgeschmissenen Zahlen einfach auf 0 bzw. False/True setzt (wie @RodFromGermany: schon schrieb). So veränderst du nicht jedes mal den Listenindex.
    Auf Wikipedia gibt es einen Pseudocode, den du praktisch nur in C# umwandeln musst.

    Quellcode

    1. const N = 10000
    2. var gestrichen: array [2..N] of boolean
    4. // Initialisierung des Primzahlfeldes
    5. // Alle Zahlen im Feld sind zu Beginn nicht gestrichen
    6. for i = 2 to N do
    7. gestrichen[i] = false
    8. end
    10. for i = 2 to N do
    11. if not gestrichen[i] then
    12. // i ist prim, gib i aus
    13. print i; ", ";
    14. // und streiche seine Vielfachen, beginnend mit i*i
    15. // (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
    16. for j = i*i to N step i do
    17. gestrichen[j] = true
    18. end
    19. end if
    20. end

    Du brauchst in der Liste ja auch nicht die Zahlen haben, denn du hast ja den Index, aus dem die Zahlen folgen. Deshalb arbeitet man hier am besten mit einem Boolean-Array. Dort "streichst" du die einzelnen Zahlen, indem du beim Array den Wer am Index der Zahl auf False/True setzt. Am Ende musst du nur alle ausgeben, die nicht False/True sind.
    Von meinem iPhone gesendet

Facebook
Telefonspende