[.NET] [C#] - Sieb des Eratosthenes

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von juppwatis, 24. September 2007 .

Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 24. September 2007
    [C#] - Sieb des Eratosthenes

    hi @ all

    ich habe einen Primzahlrechner geschrieben. Dann hat mir wer gesagt, dass der Sieb des Eratosthenes besser ist. jetzt versuche ich mich gerade den mal zu coden, jedoch komme ich nicht wirklich weiter bzw weiß ich nicht so recht, wie ich das realisieren kann. ich hab mir das so gedacht:

    1. int "variable" grenze deklarieren
    2. int array machen, in welchem der wert von "grenze" ist.
    3. benutzer gibt die grenze ein

    nehmen wir an, der benutzer gibt 100 ein. dann ist das array quasi 100 elemente oder? so weiter...

    4. bei 2 beginnen und von 2 alle vielfachen speichern, damit es keien primzahlen können.
    5. mit 3 weitermachen, vielfache speichern usw..

    jetzt die frage: wie speicher ich die vielfachen? hab keine ahnung, wie ich das machen soll
    kann mir wer en tipp oder so geben?

    mfg
     
  3. 24. September 2007
    AW: [C#] - Sieb des Eratosthenes

    Einfach alle Zahlen durchlaufen.

    Wenn du z.B. schauen willst, ob eine Zahl durch zwei Teilbar ist, einfach "Zahl MOD 2" rechnen. Mod ist 0 wenn sie durch 2 teilbar ist, und != 0 wenn sie nicht durch 2 teilbar ist.
    Und so machst du das bei jeder Zahl.
    Bei 3 isses das gleiche: "Zahl MOD 3", 3 != 0 -> kein Vielfaches, Zahl == 0 -> Vielfaches.
     
  4. 24. September 2007
    AW: [C#] - Sieb des Eratosthenes


    so funktioniert aber doch nicht der sieb des eratosthenes. da fängt man mit der zahl zwei an. davon nimmt man alle vielfache: 2,4,6,8,... diese zahlen können dann automatische schon keine primzahlen mehr werden. diese vielfache werden dann bis zur grenze, die man eingegeben hat berechnet. danach folgt die nächste zahl, die noch nicht "markiert" wurde, also kein vielfaches von 2 war. in dem fall die 3 -> somit hat man schon die nächste primzahl. dann nimmt man von 3 alle vielfache, d.h. diese scheiden dann als primzahlen auch aus. und so machen man das weiter. als nächstes wäre die 4 dran, aber die wurde ja schon als vielfaches von 2 identifiziert und somit gehts mit 5 weiter....

    weiß wer, wie ich das coden kann? ich komme einfach nicht drauf

    mfg
     
  5. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    Hi...

    also ich versuchs mal als Pseudo Code:

    Code:
     

bool[] deineZahlen= new bool[grenze];

//Alles im Array auf true setzen (außer 1 da definitiv keine Primzahl), danach vielfache einer Zahl auf false


//Berechnung
fürAlleZahlen (zahl = 2; zahl < grenze: zahl um 1 erhöhen)
{
 //Fall das die aktuelle Zahl kein Vielfaches einer anderen Zahl war, also eine Primzahl ist
 wenn(deineZahlen[zahl] = true)
 {
 //Berechnung der Vielfachen 
 tempZahl = 2
 solange ((tempZahl = zahl*tempZahl) < grenze)
 {
 deineZahlen[tempZahl] = false; //keinePrimzahl
 
 }
 }
 sonst
 {
 machDenNächstenDurchlauf
 }
}

//für die Ausgabe das Array durchlaufen und immer den Index der Stelle ausgeben, an dem noch true steht
    Hoffe es funktioniert. Bin schon ziemlich müde, deswegen kann ich es nicht garantieren. Kommt natürlich auch auf die Umsetzung an . Aber wenn ich mich recht erinnere kann man das so machen.

    Ne BW wäre nice.

    Mfg
    Sinus2K

    EDIT: Habs mal eben in Java getestet und irgendwo ist da noch der Wurm drin. Aber vielleicht reichts ja als Denkhilfe.
     
  6. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    so bw ist natürlich raus. aber ich kapier es nicht. hab versucht deinen code mal umzusetzen aber ich komm gar nicht damit klar
    eigentlich will ich ja gar keinen code, sondern nur ne shcöne beschreibung, was ich nacheinander machen muss. ich check das absolut nicht

    wie setze ich denn den ganzen array auf true? das ist schonmal mein erstes großes rätsel!und es gibt noch viel mehr :-!

    mfg
     
  7. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    also ich glaub ich weiss wer der jenige ist, der dir das mit dem sieb des erathostens gesagt hat

    hier ist die methode, aber in java: (wie in dem letzen thread schon geschrieben, ich kenne mich in c# nicht aus)

    Code:
    static void showPrimes(int max) {
 boolean[] sieb = new boolean[max+1];
 int i, j;
 for(i=2; i<=max; i++) sieb[i] = true;
 i = 2;
 while(i<=max) {
 System.out.println(i + " "); //i ist prim
 for(j=i; j <= max; j = j+1) sieb[j] = false;
 while( i <= max && !sieb[i]) i++;
 }
}
     
  8. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    wenn, dann machs biite auch richtig, 2 ist eine primzahl.
     
  9. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    das weiß ich auch. aber deinen kl anmerkung am rande bringt mich jetzt kein bisschen weiter! :-!
     
  10. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    c++.de :: Sieb des Eratosthenes - Segmentation fault

    hab mal geguugelt, vllt kannste am dem quelltext was lernen!

    Knusperkeks
     
  11. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    den hab ich auch schonmal gesehen aber ich kann darin absolut nicht den sieb des eratosthenes erkennnen irgendwie. weiß auch nicht...aber thx
     
  12. 25. September 2007
    AW: [C#] - Sieb des Eratosthenes

    Code:
    enum PrimeType { Prime, NotPrime };
static PrimeType[] Eratosthenes(int maxPrime)
 {
 // wird automatisch zu 0 also Prime intitialisiert
 PrimeType[] primes = new PrimeType[maxPrime];
 for (int p = 2; p*p < maxPrime; p++) {
 if (primes[p] == PrimeType.Prime)
 {
 // streichen
 for (int k = 2; p * k < maxPrime; k++)
 primes[p * k] = PrimeType.NotPrime;
 }
 
 }
 return primes;
 }
    bitteschön
     
  13. 26. September 2007
    AW: [C#] - Sieb des Eratosthenes

    jetzt ist halt bei deinem code die frage, was in welchen codeblock gehört? bzw fehlen da codeblöcke? bei der ersten for-schleife...was gehört da alles dazu? dein code kann ja kein normaler mensch gescheit lesen
    wäre nice, wenn du den mal schön formatieren könntest...

    mfg
     
  14. 26. September 2007
    AW: [C#] - Sieb des Eratosthenes

    der ist wunderbar formatiert!

    Das ist die ganze for schleife:
    Code:
    for(i=2; i<=max; i++) sieb[i] = true;
    die for schleife steht in einer zeile da sie nicht viel enthält und der rest ist eingerückt!

    Sollte also leit zu lesen sein!

    hier nochmal mit farbe:

    Code:
    [COLOR="DarkOrange"]static void showPrimes(int max) {
 boolean[] sieb = new boolean[max+1];
 int i, j;[/COLOR]
 [COLOR="Red"]for(i=2; i<=max; i++) sieb[i] = true;[/COLOR]
 [COLOR="DarkOrange"]i = 2;[/COLOR]
 [COLOR="MediumTurquoise"]while(i<=max) {
 System.out.println(i + " "); //i ist prim
 for(j=i; j <= max; j = j+1) sieb[j] = false;[/COLOR]
 [COLOR="Purple"]while( i <= max && !sieb[i]) i++;[/COLOR]
 [COLOR="MediumTurquoise"]}[/COLOR]
[COLOR="DarkOrange"]}[/COLOR]
    Knusperkeks
     
  15. 26. September 2007
    AW: [C#] - Sieb des Eratosthenes

    alles klar danke. aber das programm funktioniert leider gar nicht. es gibt immer nur die zahl 2 aus.
    naja...ich probier halt mal rum...
    aber über neue lösungen würde ich mich freuen

    mfg


    //EDIT:

    also ich hab jetzt ein wenig rumprobiert und so sieht es schonmal ganz vernüftig aus:

    Code:
    using System;
using System.Collections.Generic;
using System.Text;

namespace SiebDesEratosthenes
{
 class Program
 {
 static void Main(string[] args)
 {
 int max;

 Console.Write("Bitte geben Sie eine Grenze ein: ");
 max = Int32.Parse(Console.ReadLine());

 Primzahlen(max);

 Console.ReadLine();

 }
 static void Primzahlen(int grenze)
 {
 bool[] sieb = new bool[grenze + 1];
 int i;
 
 for (i = 2; i <= grenze; i = i + 2)
 {
 sieb[i] = false; //keine Primzahlen 
 }
 sieb[0] = false; //keine Primzahlen
 sieb[1] = false; //keine Primzahlen
 

 for (i = 0; i <= grenze; i++)
 {
 if (sieb[i])
 {
 //BERECHNUNGEN AUSFÜHREN
 } 
 }
 }
 }
}
    jedoch weiß ich nicht, wie ich jetzt noch weiterrechnen soll in der if-abfrage...vll kann mir da wer weiterhelfen?

    mfg
     
  16. 27. September 2007
    AW: [C#] - Sieb des Eratosthenes

    so ich hab jetzt mal den pseudocode von wikipedia einfach genommen und geschrieben und siehe da: es funktioniert...hier der code:

    Code:
    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 + " ");
 }
 }
 }
 }
}
    jedoch habe ich jetzt noch verständnis fragen:

    1.
    Code:
    for (i = 2; i <= grenze; i++)
 {
 sieb[i] = false;
 }
    hier wird doch alles auf false gestellt oder? also alle zahlen > 2 werden auf false gestellt. wie kann es dann überhaupt noch gehen weiter unten gehen?

    wie kann denn die if-abfrage noch gehen:
    Code:
    while (i*i <= grenze)
 {
 if(!sieb[i])
 {
 for (int j = i * i; j <= grenze; j = j + i)
 {
 sieb[j] = true;
 }
 }
 i++;
 }
    die abfrage wird ja nur gemacht, wenn die werte von sieb true sind oder? aber oben haben wir ja alle bis zur grenze auf false gestellt. das geht doch nicht?

    kann mir das wer erklären? da verstehe ich absolut nicht. das programm läuft einwandfrei das hab ich schon probiert und ich denke ihr seht das auch, wenn ich c# checkt. aber für ich als anfänger ist es so gut wie unmöglich, den code nachzuvollziehen. wäre nice, wenn mir vll sogar jmd den vollständigen code, also nur die primzahlen-methode ausführlichst kommentiert.

    mfg
     
  17. 29. September 2007
    AW: [C#] - Sieb des Eratosthenes

    kann mir dazu denn keiner was sagen, bzw. kann mir keiner den code kommentieren?

    mfg
     
  18. 29. September 2007
    AW: [C#] - Sieb des Eratosthenes



    äh... nein..

    da wie du richtig bemerkt hast "sieb" für alle i >= 2 false ist, ist "!sieb" für alle i >= 2 true...

    das hier wird dir weiterhelfen:
    Logischer Operator – Wikipedia
     
  19. 2. Oktober 2007
    AW: [C#] - Sieb des Eratosthenes

    so mittlerweile habe ich es verstanden. es war ja leider keiner in der lage es mir richtig zu erklären oder bzw ausführlich.

    das

    Code:
    if (!sieb[i])
    könnte man auch als
    Code:
    if (!sieb[i] == true)
    oder
    Code:
    if (sieb[i] == false)
    schreiben. ich frage mich, warum es keiner geschafft hat es einfach so zu schreiben? anstatt immer so ein rumgerede um den heißen brei quasi. naja. danke trotzdem an all' die, die es "versucht" haben es zu erklären!

    mfg
     
  20. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.