C++ | Primzahlen

Diskutiere C++ | Primzahlen im Developer Network Forum im Bereich Hardware & Software Forum; Ich fange momentan mit C++ an :D Der nachfolgende Code ist für ein Programm, das auf eine eingegebene Zahl die nächste folgende Primzahl finden...
  • C++ | Primzahlen Beitrag #1
N

Nolath

Bekanntes Mitglied
Dabei seit
23.10.2006
Beiträge
1.121
Reaktionspunkte
1
Ich fange momentan mit C++ an :D

Der nachfolgende Code ist für ein Programm, das auf eine eingegebene Zahl die nächste folgende Primzahl finden soll.
Bis sieben geht das auch, aber danach gibt es Probleme (es dauert dann einfach ewig, aber es passiert nichts)

Hat jemand eine Idee, woran das liegen könnte?
Code:
#include<iostream>
#include<cmath>

using namespace std;

int main() {
    cout << "Berechnung der ersten Prinzahl die groesser bzw. gleich der eingegebenen Zahl ist\n";
    
    long z; //z als long deklarieren, z ist die zu untersuchende zahl
    
    do {  //endlosschleife, bis eine passende zahl eingegeben wird
        cout << "Zahl groesser 3 eingeben: ";
        cin >> z;
       } while( z <= 3);
       
     if (z % 2 == 0) { //feststellen ob z gerade ist (restwerdivision)
           ++z;
           }
     bool gefunden = false; //gefunden als bool (wahr/falsch) deklarieren
     
     do {
         /* bis limit muss gerechnet werden, sqrt arbeitet nur mit double,
         also muss der Typ explizit umgewandelt werden. */
         
         long limit = 1 + static_cast<long>(sqrt(static_cast<double>(z)));
         
         long rest;
         long teiler = 1;
         
         do {
             teiler += 2;
             rest = z % teiler;
             } while( rest > 0 && teiler > limit);
         if( rest > 0 && teiler >= limit)
             gefunden = true;
         else
             z +=2;
             } while(!gefunden);
         cout << "Die nächste Primzahl ist " << z << endl;
         
         system("Pause");
         
         }
 
  • C++ | Primzahlen Beitrag #2
Lambo-Benni

Lambo-Benni

Bekanntes Mitglied
Dabei seit
23.03.2007
Beiträge
7.601
Reaktionspunkte
3
Ort
Medizinmanndiscount
ich habe jetzt den Fehler bei Dir nicht finden können - bin auch noch Newibie, aber ein Tipp:

mach doch die Berechnung der nä. Primzahl mit "for"...

for (i = 2 ; (z % i == 0) || (i == z) ; ++i) {...bla...} ;)
 
  • C++ | Primzahlen Beitrag #3
N

Nolath

Bekanntes Mitglied
Dabei seit
23.10.2006
Beiträge
1.121
Reaktionspunkte
1
ich habe jetzt den Fehler bei Dir nicht finden können - bin auch noch Newibie, aber ein Tipp:

mach doch die Berechnung der nä. Primzahl mit "for"...

for (i = 2 ; (z % i == 0) || (i == z) ; ++i) {...bla...} ;)

In C++ lässt sich jede do in eine for und in eine while schliefe umwandeln...

Ich kann jede Schleife mal ausprobieren, aber ich denke nicht, dass es einen Unterschied machen wird.
 
  • C++ | Primzahlen Beitrag #4
Lambo-Benni

Lambo-Benni

Bekanntes Mitglied
Dabei seit
23.03.2007
Beiträge
7.601
Reaktionspunkte
3
Ort
Medizinmanndiscount
Ich denke nur, dass es einfacher und übersichtlicher wäre - deutlicher weniger Code.
 
  • C++ | Primzahlen Beitrag #5
N

nic_power

Senior Moderator
Dabei seit
27.12.2000
Beiträge
7.838
Reaktionspunkte
2
Hallo,

Ich fange momentan mit C++ an :D

Der nachfolgende Code ist für ein Programm, das auf eine eingegebene Zahl die nächste folgende Primzahl finden soll.
Bis sieben geht das auch, aber danach gibt es Probleme (es dauert dann einfach ewig, aber es passiert nichts)

Hat jemand eine Idee, woran das liegen könnte?

Ich habe mir Dein Programm nicht im Detail angeschaut, habe aber einen Tip (aka "Idee") zur Fehlereingrenzung.

Das Problem ist, dass Du den Bereich in dem Du nach einer Primzahl suchen möchtest nicht kennst (da du ja die nächste Primzahl suchst und nicht testen möchtest, ob es sich bei der aktuellen Eingabe um eine Primzahl handelt). Damit liegt der zu Durchsuchende Bereich zwischen "Eingabe+1" und "unendlich".

Der Übersichtlichkeit halber würde ich erstmal den Primzahlentest getrennt vom Rest des Programms implementieren (in einer eigenen Funktion, beispielsweise "bool istPrimzahl(int zahl)", diese Funktion nimm ein Argument und liefert entweder "true" oder "false" zurück). [1]

Die Hauptschleife könntest Du dann in der folgenden Form realisieren:

Code:
while (!istPrimzahl(testZahl)) {
  testZahl++;
}
Du kannst natürlich auch optimieren, in dem Du beispielsweise alle geraden Zahlen auslässt, die Schleife bei einer ungeraden Zahl anfangen lässt und immer um "2" erhhöhst.

Nic

[1]
Die gretrennte Implementierung ist aus Performance-Sicht zwar nicht optimal, fördert aber die Übersicht und sollte hier auch erstmal unkritisch sein.
 
  • C++ | Primzahlen Beitrag #6
N

Nolath

Bekanntes Mitglied
Dabei seit
23.10.2006
Beiträge
1.121
Reaktionspunkte
1
Ich habe es so gemacht, doch es ging immer noch nicht.
Dann habe ich in jede 2. Zeile einen Kommentar eingefügt und geschaut bis zu welchem es geht.
Das Ergebnis war, dass alle Kommentare in Höchsgeschwindigkeit hintereinander ausgegeben wurden.
Also habe ich in den Do-Schleifen Zeile für Zeile geändert und kam zu dem Ergebnis, dass es an der letzten Zeile lag, die } while(!gefunden);
Das habe ich dann einfach in gefunden = false geändert:
Jetzt geht die Berechnung schnell und ohne Probleme.

Code:
[...]
         do {
             teiler += 2;
             rest = z % teiler;
             } while( rest > 0 && teiler > limit);
         if( rest > 0  >= limit)
             gefunden = true;
         else
             z +=2;
[B]             } while(gefunden = false);[/B]
         cout << "Die nächste Primzahl ist " << z << endl;
         
         system("Pause");
         
         }


Danke für eure Hilfe :goil:
 
  • C++ | Primzahlen Beitrag #7
Lambo-Benni

Lambo-Benni

Bekanntes Mitglied
Dabei seit
23.03.2007
Beiträge
7.601
Reaktionspunkte
3
Ort
Medizinmanndiscount
Also habe ich in den Do-Schleifen Zeile für Zeile geändert und kam zu dem Ergebnis, dass es an der letzten Zeile lag, die } while(!gefunden);
Das habe ich dann einfach in gefunden = false geändert:
Aber als Newbie habe ich noch eine Frage: Ist das nicht das gleiche nur anders geschrieben?
 
  • C++ | Primzahlen Beitrag #8
N

Nolath

Bekanntes Mitglied
Dabei seit
23.10.2006
Beiträge
1.121
Reaktionspunkte
1
Aber als Newbie habe ich noch eine Frage: Ist das nicht das gleiche nur anders geschrieben?

Das dachte ich auch.

Durch das "!" wird der Wert von gefunden (false) negativiert. Das Gegenteil von false ist true.
Bei gefunden = false, wird der Wert exakt zugewiesen.


Keine Ahnung, was daran in dem Fall der Unterschied ist xD
 
  • C++ | Primzahlen Beitrag #9
N

nic_power

Senior Moderator
Dabei seit
27.12.2000
Beiträge
7.838
Reaktionspunkte
2
Hallo,

Aber als Newbie habe ich noch eine Frage: Ist das nicht das gleiche nur anders geschrieben?
Nein, das ist der beliebteste Anfängerfehler in C!

while (!gefunden) {} ...
Wird die Schleife solange durchlaufen, bis die Bedingung "!gefunden" zutrifft.

while (gefunden=false) {}
Hier wird "gefunden" der Wert "false" zugewiesen, also könnte man auch "while(false) {}" schreiben; d.h. die Schleife wird überhaupt nicht durchlaufen! Vergleich in C benötigen "=="!


Nic
 
  • C++ | Primzahlen Beitrag #10
N

Nolath

Bekanntes Mitglied
Dabei seit
23.10.2006
Beiträge
1.121
Reaktionspunkte
1
Hallo,


Nein, das ist der beliebteste Anfängerfehler in C!

while (!gefunden) {} ...
Wird die Schleife solange durchlaufen, bis die Bedingung "!gefunden" zutrifft.

while (gefunden=false) {}
Hier wird "gefunden" der Wert "false" zugewiesen, also könnte man auch "while(false) {}" schreiben; d.h. die Schleife wird überhaupt nicht durchlaufen! Vergleich in C benötigen "=="!


Nic

Thx, habe das auch gestern feststellen müssen.

Das Programm funktioniert dann nämlich nicht mehr :D
Ich hatte nur gedacht, dass es funktioniert, da ich 8 eingegeben habe und 11 als Ergebnis kam.

So gesehen funktioniert es wieder nicht...
 
  • C++ | Primzahlen Beitrag #11
cmddegi

cmddegi

Bekanntes Mitglied
Dabei seit
12.07.2001
Beiträge
4.740
Reaktionspunkte
0
Ort
Austria
Sollte die Schleifenbedingung hier
Code:
do {
             teiler += 2;
             rest = z % teiler;
             } while( rest > 0 && teiler > limit);
nicht
Code:
while( rest > 0 && teiler < limit)
sein?

btw.: Eine automatische Zeilennumerierung bei den code-Tags wäre toll. ;)
 
Thema:

C++ | Primzahlen

ANGEBOTE & SPONSOREN

https://www.mofapower.de/

Statistik des Forums

Themen
213.180
Beiträge
1.579.174
Mitglieder
55.879
Neuestes Mitglied
stonetreck
Oben