014
22.07.2006, 21:20 Uhr
virtual
Sexiest Bit alive
(Operator)
|
| Zitat von Rumak18: |
Das denke ich mir auch,vor allem wenn ich bedenke,dass man doch bestimmt keine Klassen für die Lösung dieser Aufgabe braucht. @virtual: Ich weiss erstens immer noch nicht,was ich in meinen "verbesserten" Quellcodes falsch habe, ausserdem stimmt ja deiner nicht,wenn nur 1 und 2 als Primzahlen ausgegeben werden.
|
Hallo,
ich hatte das Programm nicht getestet und prompt auch einen Fehler reingebaut. Richtig wäre vermutlich (wieder ohne Test):
| C++: |
for(int zahl=1; zahl<200; ++zahl) {
bool isPrime = true;
for(int i=2; i<zahl && isPrime; ++i) {
isPrime = zahl%i != 0; // Hier stand == anstelle von !=
}
if (isPrime) std::cout<<zahl<<std::endl;
}
|
Wobei bei der inneren Schleife - der eigentliche Primzahltest hochgradig Optimierungspotential drin ist. Zur weiteren Klärung:
Eine Zahl ist eine Primzahl, wenn sie genau zwei Teiler hat (nämlich1 und sich selbst). In jüngerere Zeit definiert man daß 1 keine Primzahl ist, früher hatte man 1 auch als Primzahl angesehen. Ist letztlich eine reine Definitionsfrage. Wie dem auch sei: eine zahl N ist somit Primzahl, wenn es keine Zahl zwischen 2 und N-1 gibt, durch die sich N restlos Teilen ließe. Formal also
| Code: |
n ist Primzahl <=> für alle 2<=i<n: n%i!=0
|
Genau dies drückt der innere Teil der Schleife aus. Dh es ist jedenfalls notwenig, wirklich alleZahlen zwischen 2 und N-1 zu überprüfen, ob N eine Primzahl ist. Wie Du unschwer anhand deines Codes sehen kannst, machst du das nicht.
Wenn ich nun sage, daß man alle Zahlen zwischen 2 und N-1 überprüfen müsste, ist das natürlich nicht ganz wahr:
Angenommen, n wäre keine Primzahl, also als Produkt zweier Zahlen a,b >=2 darstellbar: N= a*b, dann kann man beweisen, daß mindestens eine der beiden Zahlen gleichzeitig kleiner oder gleich de Wurzel von N ist (dementsprechend die andere größer oder gleich). Deshalb kann man den zu testenden Zahlenbreich schon man auf 2-sqrt(N) einschränken. Üblicherweise kann mann noch weitere Einschränkungen machen, zB daß man diesen Zahlenbreich mit einer bstimmten Schrittgröße durchmisst und nicht wirklich jede Zahl prüfen muß, dh man kann noch optimieren.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
