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

juppwatis · 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

Anzeige

pyro · 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.

juppwatis · 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

Sinus2K · 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.

juppwatis · 25. September 2007

AW: [C#] - Sieb des Eratosthenes

Zitat von Sinus2K: ↑

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
Klicke in dieses Feld, um es in vollständiger Größe anzuzeigen.

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

litux · 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++;
 }
}

didda · 25. September 2007

AW: [C#] - Sieb des Eratosthenes

wenn, dann machs biite auch richtig, 2 ist eine primzahl.

juppwatis · 25. September 2007

AW: [C#] - Sieb des Eratosthenes

das weiß ich auch. aber deinen kl anmerkung am rande bringt mich jetzt kein bisschen weiter! :-!

Knusperkeks · 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

juppwatis · 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

naca7 · 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

juppwatis · 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

Knusperkeks · 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

juppwatis · 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

juppwatis · 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

juppwatis · 29. September 2007

AW: [C#] - Sieb des Eratosthenes

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

mfg

Timer · 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

juppwatis · 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

Nützliche Suchen

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

Videos zum Themenbereich