C++ Primzahlen suchen

[Tryharder]

Hallo Leute,

Ich habe ein Problem mit diesem Code

cout << "n angeben.\n";		// die ersten n Primzahlen finden
int n;
cin >> n;
int count = 0;
int x = 0;
vector<int> primzahlen;

for(int zahl = 3; x<=n; ++zahl){	// Wenn x kleiner oder gleich n ist wird mit dem suchen aufgehört

	for(int probe = 2; probe < zahl; ++probe){		// jede Zahl wird durch eine "probezahl" geteilt
		if(zahl%probe == 0)							// Kein Rest, dann Primzahl
			++count;
	}
	if(count == 0){									// Wenn count unverändert, dann zahl in vector gespeichert
			primzahlen.push_back(zahl);
			count = 0;								// Initialwert zuweisen
			++x;									// ++x erhöhen, es muss ja irgendwann die Bedingung in der ersten Schleife erfüllt werden
		}
}

for(unsigned int i = 0; i < primzahlen.size(); ++i)			
	cout << primzahlen[i] << endl;						// Zahlen werden ausgegeben

Aus irgendeinem Grund wird keine Primzahl ausgegeben, obwohl ich mir sicher bin, dass ich keinen Fehler gemacht habe(vllt. Logikfehler). Ich habe eine andere Version zum Primzahlen suchen geschrieben, welche Primzahlen bis zu einem Limit sucht, und diese Version funktioniert makellos.
Es wäre sehr nett, wenn sich jemand die Zeit nimmt und den Fehler entdeckt.

mfg, tryharder

[SeppJ]

Scope zu groß gewählt. Schieb Zeile 4 nach Zeile 9.

Dein Algorithmus findet die 2 nicht.

Es wäre übrigens schöne, wenn du Programme vollständig postest, so dass man sie direkt kopieren und ausführen kann, ohne selber noch Code ergänzen zu müssen. Auch oder gerade bei solch kleinen Progrämmchen. Das macht es wesentlich leichter, dir zu helfen.

[Fytch]

zeile 8:
"// Wenn x kleiner oder gleich n ist wird mit dem suchen aufgehört weitergesucht"

zeile 10:
du musst nur bis sqrt(n) gehen.

zeile 11:
eine primzahl ist es natürlich nur wenn n mod x UNGLEICH 0 für x > 2 und x < n. also:
"// Kein Rest, dann keine Primzahl"

ich durchblicke dein system mit count usw. nicht ganz.

[Fytch]

hier mal meine unschöne aber verständliche lösung:

#include <iostream> 
#include <vector> 
int main() 
{ 
    unsigned n; 
    std::cin >> n; 
    std::vector<unsigned> Primes(n >= 1, 2); 
    for(unsigned Candidate = 3; Primes.size() < n; ++Candidate) 
    { 
        bool IsPrime = true; 
        for(unsigned Divisor = 2; Divisor * Divisor <= Candidate; ++Divisor) 
        { 
            if(Candidate % Divisor == 0) 
            { 
                IsPrime = false; 
                break; 
            } 
        } 
        if(IsPrime) 
        { 
            Primes.push_back(Candidate); 
        } 
    } 
    for(std::size_t i = 0; i < Primes.size(); ++i) 
    { 
        std::cout << Primes[i] << '\n'; 
    } 
}

http://ideone.com/QK97BO

frage, wenn du fragen dazu hast.

edit: es geht darum es so zu lösen dass der te es versteht, nicht darum möglichst effizient zu sein. lohnt sich also nicht einen neuen thread zu machen deswegen...

edit 2: ich hab es nicht richtig gelesen, sorry.

[SeppJ]

Der TE will aber N Primzahlen finden, nicht Primzahlen bis N

[Fytch]

SeppJ schrieb:

Der TE will aber N Primzahlen finden, nicht Primzahlen bis N

oh wie dumm von mir. ich habs angepasst. danke für den hinweis.

[Tryharder]

Danke fürs Feedback erstmal,

asfdlol: Mit dem count, der testet z.b 6%2, was ja 0 ergibt, dann wird der wert von count um 1 erhöht. So in zeile 14 wird getestet, ob count == 0 ist, also ob der Wert nicht erhöht wurde. Wenn das stimmt, dann wird die Zahl ausgegeben.
Schließlich wird count wieder auf den Initialwert gebracht, damit man das gleiche mit der nächsten Zahl machen kann.
Dein Programm habe ich auch geschrieben, aber etwas anderes. Das Programm gibt mir aber alle Primzahlen bis zur Zahl n an. Ich will aber die ersten primzahlen ausgegeben bekommen.
Danke für die Korrekturen in den Kommentaren.

SeppJ: Vielen Dank :).
Könntest du mir genauer erklären was da verändert wird?
Der gesamte Code:

#include "../../../std_lib_facilities.h"
#include <conio.h>

int main () {
cout << "n angeben.\n";     // die ersten n Primzahlen finden
int n;
cin >> n;
int x = 0;
vector<int> primzahlen;

for(int zahl = 3; x<n; ++zahl){   
   int count = 0;
    for(int probe = 2; probe < zahl; ++probe){      // jede Zahl wird durch eine "probezahl" geteilt
        if(zahl%probe == 0)                         // Kein Rest, dann Primzahl
            ++count;
    }
    if(count == 0){                                 // Wenn count unverändert, dann zahl in vector gespeichert
            primzahlen.push_back(zahl);
            count = 0;                              // Initialwert zuweisen
            ++x;                                    // ++x erhöhen, es muss ja irgendwann die Bedingung in der ersten Schleife erfüllt werden
        }
}

for(unsigned int i = 0; i < primzahlen.size(); ++i)        
    cout << primzahlen[i] << endl;                      // Zahlen werden ausgegeben

	_getch();
	keep_window_open();
	}

[tryharder]

Upps zu spät gelesen, erster Abschnitt hat sich ja geklärt (nur Gast, kann nicht editieren :/)

[SeppJ]

Tryharder schrieb:

Könntest du mir genauer erklären was da verändert wird?

Ist das nicht selbsterklärend? Beim ursprünglichen Code wird count einmal ganz am Programmanfang auf 0 gesetzt. Beim neuen Code wird es zu Beginn jedes Durchlaufs auf 0 gesetzt.

Jetzt denk mal darüber nach, wieso dein ursprünglicher Code nicht funktioniert hat, wenn count nur am Anfang auf 0 gesetzt wurde. Geh mal im Kopf durch, welche Werte count dann nach jedem Durchlauf hat.

[Tryharder]

Dann ist Zeile 20 ja obsolet. Ok danke

[Fytch]

Tryharder schrieb:

Dann ist Zeile 20 ja obsolet. Ok danke

sie ist ziemlich sinnlos ehrlich gesagt. schau dir mal an was die bedingung ist dass diese zeile aufgerufen wird. und vergleiche es mit der zeile selbst.

[Tryharder]

Ich frage aus Interesse, und das hat nur bedingt mit dem Topic zu tun.

Passiert es später auch auf einem höheren C++ level, dass solche groben Logikfehler gemacht werden und das z.B. ein Projekt immens verlangsamt?
Oder werden diese Fehler mit viel Übungen kaum begangen?

[Tryharder]

Jo, wieso 0 zuweisen, wenn sie schon 0 ist haha.

[SeppJ]

Tryharder schrieb:

Passiert es später auch auf einem höheren C++ level, dass solche groben Logikfehler gemacht werden und das z.B. ein Projekt immens verlangsamt?
Oder werden diese Fehler mit viel Übungen kaum begangen?

Kommt drauf an, welche Art von Logikfehler. Fehler in der Programmlogik hat man auf hohem C++-Niveau eher selten, da man C++ so programmieren kann, dass Logikfehler zu Compilerfehlern werden. Logikfehler in dem Sinne, dass man die falsche Vorgehensweise für etwas wählt kann man hingegen auf jedem Niveau haben und hat nichts direkt mit der Sprache zu tun. Aber ein erfahrener Programmierer macht diese Art von Fehler trotzdem seltener, weil er eben mehr Erfahrung hat und viele Probleme schon einmal gelöst hat und die beste Lösung kennt. 99% vieler Problemlösungen sind neu zusammen gesetzte bekannte Lösungen alter Probleme und dann noch 1% Anpassung auf das aktuelle Problem. Du wirst gut im Programmieren, wenn du viele der üblichen Probleme und ihre Lösungen kennst, dann kannst du dich mehr auf das wesentliche konzentrieren.

[Tryharder]

Ok danke für die Klarstellung .

[volkard]

Tryharder schrieb:

Passiert es später auch auf einem höheren C++ level, dass solche groben Logikfehler gemacht werden und das z.B. ein Projekt immens verlangsamt?

Viel viel seltener.

Tryharder schrieb:

Oder werden diese Fehler mit viel Übungen kaum begangen?

So ist es.

Aber man wagt sich auch an immer schwierigere Probleme, es bleibt spannend, und daß man mal ein bis zwei Tage hängt, und die Lösung nicht erzwingen kann, kommt halt vor. Leider kann man später nicht mehr im Forum fragen. Typisch, daß einem die Lösung beim Duschen einfällt, oder wenn man nachts den Kühlschrank plündert.
Hängt aber auch stark davon ab, was man so programmiert. Den lieben langen Tag Oberflächen stricken, und Du hast gar keine Probleme. Wenn der Verkäufer regelmäßig vollkommen ahnungslos Sachen verkauft, die gar nicht gehen können, oder wenn Mathematiker keine Lust haben, ihre Hausaufgaben selber zu machen und es programmieren lassen wollen, kanns ganz schön nichtamüsierend sein.

[Tryharder]

volkard schrieb:

Aber man wagt sich auch an immer schwierigere Probleme, es bleibt spannend, und daß man mal ein bis zwei Tage hängt, und die Lösung nicht erzwingen kann, kommt halt vor. Leider kann man später nicht mehr im Forum fragen.

Sicherlich, aber man hat bestimmt Kollegen die gerne mal rüber gucken.

[mgaeckler]

Tryharder schrieb:

Ich frage aus Interesse, und das hat nur bedingt mit dem Topic zu tun.

Passiert es später auch auf einem höheren C++ level, dass solche groben Logikfehler gemacht werden und das z.B. ein Projekt immens verlangsamt?
Oder werden diese Fehler mit viel Übungen kaum begangen?

Fehler können jedem passieren. Aber es ist klar, daß es immer weniger werden, je mehr Erfahrung man/frau hat. Aber auch mit viel Erfahrung kann man/frau mal 'nen schlechten Tag erwischen. Allerdings kennt man halt seine Werkzeuge. Spätestens mit einem Debugger hättest auch Du den Fehler schnell gefunden. Daher frage ich mich auch immer wieder, warum so viele Anfänger, bevor sie den Debugger anwerfen, hier im Forum nachfragen.

Darüber hinaus schreit Dein Code nach Optimierung. Wenn ich sowas sehe, frage ich mich, ob Ihr von Intel bezahlt werdet, möglich ineffiient zu programmieren, damnit Eure Anwender möglichst schnelle CPUs brauchen.

1. Für die Bestimmung ob x eine Primzahl ist, brauchst Du nicht die Anzahl der Teiler sondern es genügt, beim ersten Treffer die Suche abzubrechen. Dann ist nämlich x keine Primzahl.
2. Ebenso ist es nicht notwendig teiler > sqrt( x) zu untersuchen. Denn wenn Du bei teiler <= sqrt( x ) nicht fündig warst, findest Du auch in diesem Bereich keinen.
3. Da Du eh schon eine Liste aller Primzahlen kleiner x hast, genügt es auch sich auf Teiler in Primzahlen zu beschränken. Denn wenn eine Zahl y kein Teiler von x ist sind das auch alle vielfache von y nicht. Da alle Zahlen, die nicht in Deiner Primahlenliste sind ein Vielfaches von mindestens einer Zahl in Deiner Primzahlenliste ist kannst Du die die POrüfung sparen.
4. Gerade Zahlen brauchst Du auch nicht untersuchen also beschränke dich auf ungerade Zahlen:

for( x=3; n<max; x+=2 )

mfg Martin

[Fytch]

mgaeckler schrieb:

Darüber hinaus schreit Dein Code nach Optimierung. Wenn ich sowas sehe, frage ich mich, ob Ihr von Intel bezahlt werdet, möglich ineffiient zu programmieren, damnit Eure Anwender möglichst schnelle CPUs brauchen.

ich glaube, er hat nirgends gefragt wie man den code laufzeittechnisch optimieren kann, da gäbe es auch wesentlich bessere methoden (zumal du das vermutliche bottleneck bei der probedivision-implementierung - das stückweise allozieren im vector - nicht nanntest): siebe.

[SeppJ]

mgaeckler schrieb:

Darüber hinaus schreit Dein Code nach Optimierung. Wenn ich sowas sehe, frage ich mich, ob Ihr von Intel bezahlt werdet, möglich ineffiient zu programmieren, damnit Eure Anwender möglichst schnelle CPUs brauchen.

Offtopic: Gerade CPU-Hersteller sind unter den besten Anlaufstellen, wenn es um Optimierung geht. Der entscheidende Verkaufspunkt von CPUs ist, dass Software möglichst schnell auf ihnen läuft. Die Hersteller verwenden daher reichlich Energie darauf, dass möglichst viel Software möglichst schnell auf ihren CPU läuft.

[volkard]

asfdlol schrieb:

(zumal du das vermutliche bottleneck bei der probedivision-implementierung - das stückweise allozieren im vector - nicht nanntest): siebe.

Das Stückweise vergrößern eines std::vector mit push_back ist NICHT lahm.