Das Programm sieht bis auf ein paar Kleinigkeiten ganz gut aus:
1. Die Konstante 100 taucht zweimal auf. Wenn du die Primzahlen bis 1000
berechnen möchtest, musst du das Programm deswegen an zwei Stellen
ändern und wehe, du vergisst eine davon. Besser ist es, der Konstante
einen Namen (bspw. n) zu geben.
2. Da der Vektor für jedes Element nur die Information "ist prim" bzw.
"ist nicht prim" enthalten muss, genügen Bool-Werte. Das spart bei
großen n viel Speicher, vor allem dann, wenn die einzelnen Bool-Werte
als gepackte Bits gespeichert werden, wie es bei den meisten neueren
Implementationen der C++-Standardbibliothek der Fall ist.
3. Da in diesem Fall alle Elemente bis auf die ersten beiden den
gleichen Initialisierungwert (true) bekommen, kann man die
Initialisierung gleich im Konstruktor von vector vornehmen.
4. Es müssen nicht die Vielfachen von jeder Zahl, sondern nur die
Vielfachen der Primzahlen herausgestrichen werden. Die jeweils
nächste Primzahl findet man leicht durch lineare Suche in primes.
5. Mit dem Herausstreichen der Zahlen muss man nicht beim Doppelten,
sondern kann beim Quadrat der aktuellen Primzahl beginnen. Alle
kleineren Vielfachen wurden bereits in früheren Schleifendurchläufen
herausgestrichen.
6. Ist das Quadrat der aktuellen Primzahl größer als der größte Index in
primes, ist der Siebalgorithmus abgeschlossen.
7. endl unterscheidet sich von '\n' in einem ostream (cout) dadurch,
dass es den Stream zusätzlich flusht. Insbesondere beim Schreiben von
Dateien kostet der Flush nicht unerheblich Zeit, weswegen dort
i.Allg. '\n' vorzuziehen ist. Bei der Bildschirmausgabe spielt das
keine Rolle, aber vielleicht möchtest du die Ausgabe Primzahlen auch
einmal in eine Datei umleiten. Deswegen nehme ich standardmäßig immer
'\n' statt endl, es sei denn, es gibt spezielle Gründe für den Flush.
8. Du verwendest vector, cout und endl ohne die Angabe des Namespace
(std::). Falls du dafür ein "using namespace std;" machst, ist das
bei diesem Mini- und Wegschmeißprogramm in Ordnung, aber lies dir
dieses durch:
http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice
Besser ist es, jedem Symbol auf der Standardbibliothek den Präfix
std:: voranzustellen (was leider Sch... aussieht) oder die
tatsächlich benutzten Symbole einzeln mit "using std::vector;",
"using std::cout;" usw. bekannt zu machen (was leider viel
Schreibarbeit ist).
Hier ist eine Modifikation deines Programms mit Berücksichtigung der
obigen Punkte:
1 | #include <iostream>
|
2 | #include <vector>
|
3 |
|
4 | int main() {
|
5 | const int n = 100;
|
6 | std::vector<bool> primes(n, true);
|
7 | primes[0] = primes[1] = false;
|
8 |
|
9 | // Sieb des Erastosthenes
|
10 | int step = 0;
|
11 | while(true) {
|
12 | while(!primes[++step]); // nächste Primzahl suchen
|
13 | int startval = step * step;
|
14 | if(startval >= n)
|
15 | break;
|
16 | for(int i=startval; i<n; i+=step)
|
17 | primes[i] = false;
|
18 | }
|
19 |
|
20 | // Gefundene Primzahlen zur kontrolle ausgeben
|
21 | for(int i=0; i<n; ++i) {
|
22 | if(primes[i])
|
23 | std::cout << i << '\n';
|
24 | }
|
25 |
|
26 | return 0;
|
27 | }
|
Dank der oben beschriebenen Optimierungen des Algorithmus läuft das
geänderte Programm für n=10000000 (10⁷) ohne die Ausgabe der Ergebnisse
etwa um den Faktor 80 schneller.
