Hi,
ich stehe atm vor der aufgabe, ein programm zu schreiben, welches mir alle primzahlen von 2 - n berechnet. dabei bin ich auf den algorithmus des eratosthenes (aka sieb des eratosthenes) gestoßen
bei diesem wird die wurzel aus n gezogen, und dann die erste primzahl gesucht, wenn diese gefunden wird, werden alle vielfachen dieser, gestrichen, right?
wie stell ich das am besten an? - könnt ihr mir 'ne art denkanstoß o.ä. geben? =)
Seite 1 von 1
C#: Sieb Des Eratosthenes - Primzahlenberechnung
Anzeige
#2
geschrieben 28. Februar 2007 - 08:22
Ah, das habe ich damals in der Berufsschule gemacht, sogar in C# (Quellcode müsste eigentlich noch irgendwo rumfliegen).
Hier zu deinem Denkanstoß.
Nimm ein boolsches Array der Länge n (kannst auch n+1 nehmen, wegen der 0).
Fängst mit 2 an.
Gehst das Array durch und setzt sämtliche Vielfachen von 2 auf false.
Nimmst die 3.
Gehst das Array durch und setzt sämtliche Vielfachen von 3 auf false.
Nimmst die 4.
Huch...4 ist auf false gesetzt. also weiter zur nächsten Zahl...
Und das machst du solange bis die Wurzel aus n erreicht ist (sollte glaub ich klar sein warum).
Bei der Ausgabe nimmst du nur die auf true gesetzten Felder.
(Ich bin mir gerade nicht sicher, ob boolsche Variablen standardmäßig auf true oder false gesetzt sind. Ansonsten einfach ausprobieren und ggf. anpassen)
Ach...über die Veröffentlichung deines Quellcodes würden wir uns natürlich sehr freuen
Hier zu deinem Denkanstoß.
Nimm ein boolsches Array der Länge n (kannst auch n+1 nehmen, wegen der 0).
Fängst mit 2 an.
Gehst das Array durch und setzt sämtliche Vielfachen von 2 auf false.
Nimmst die 3.
Gehst das Array durch und setzt sämtliche Vielfachen von 3 auf false.
Nimmst die 4.
Huch...4 ist auf false gesetzt. also weiter zur nächsten Zahl...
Und das machst du solange bis die Wurzel aus n erreicht ist (sollte glaub ich klar sein warum).
Bei der Ausgabe nimmst du nur die auf true gesetzten Felder.
(Ich bin mir gerade nicht sicher, ob boolsche Variablen standardmäßig auf true oder false gesetzt sind. Ansonsten einfach ausprobieren und ggf. anpassen)
Ach...über die Veröffentlichung deines Quellcodes würden wir uns natürlich sehr freuen
#3
geschrieben 02. März 2007 - 17:00
danke erstmal für deine hilfe, zu dem beispiel hab ich aber trotzdem noch so einige fragen
ich nehme ein array mit der länge n
was schreibe ich dann in das array hinein (welche werte kommen ins array?)
wie setze ich die variablen auf false?
danke
ps.: könntest du uu mal deinen quellcode posten? damit ich mir das ganze mal ansehen kann?
ich nehme ein array mit der länge n
int[] zahlenAr = new int[n];
was schreibe ich dann in das array hinein (welche werte kommen ins array?)
wie setze ich die variablen auf false?
danke
ps.: könntest du uu mal deinen quellcode posten? damit ich mir das ganze mal ansehen kann?
#4
geschrieben 02. März 2007 - 17:30
http://de.wikipedia.org/wiki/Primzahltest#...es_Eratosthenes
Einfach mal dort nachschauen. In Wiki sind viele Codebeispiele. Aber vorsicht: Nicht alle Codes sind auch richtig und funktionieren einwandfrei...
Einfach mal dort nachschauen. In Wiki sind viele Codebeispiele. Aber vorsicht: Nicht alle Codes sind auch richtig und funktionieren einwandfrei...
#5
geschrieben 03. März 2007 - 23:11
dinozzo, du sollst auch keinen array of integer machen, sondern von boolean. der index gibt die zahl an, der inhalt an der stelle x, ob zahl[x] ein array ist oder nicht.
I'm mó. mo's good twin.
#6
geschrieben 04. März 2007 - 16:39
Habe den Quellcode wieder bei mir entdeckt: http://nopaste.info/d21c602100.html
Das bringt mich wieder auf eine Idee...Parallelisieren
Das bringt mich wieder auf eine Idee...Parallelisieren
Thema verteilen:
Seite 1 von 1