Übung mit C++ - Funktion zur Identifizierung von Primzahlen mit! =

Question

Ich arbeite mich durch das Buch C++ - Programmierung Prinzipien und Praxis. In dem Buch gibt es eine Übung, Primzahlen zu finden, indem man eine Zahl mit Zahlen vergleicht, die als Primzahlen identifiziert wurden. Dies ist die Funktion, die ich geschrieben habe, um dieses Problem zu lösen.

vector <int> primes; 

int findprime (int x) { 
    for (int p=0; p<primes.size(); ++p) { 
     if (x%primes[p]!=0) { 
      return x; 
     } 
    } 
} 

int main() { 
    primes.push_back(2); 
    for (int i=3; i<100; ++i) { 
     primes.push_back(findprime(i)); 
    } 
    for (int i=0; i<primes.size(); ++i) { 
     cout << primes[i] << '\n'; 
    } 
} 

Die Autoren Funktion in seiner Lösung ist:

bool is_prime(int n) { 
    for (int p = 0; p<prime.size(); ++p) 
     if (n%prime[p]==0) return false; // no remainder: prime[p] divided 

    return true; // no smaller prime could divide 
} 

Mein Code funktioniert nicht, aber ich verstehe nicht wirklich, warum. Ich glaube, mir fehlt etwas Wissen darüber, wie die Funktionen genau funktionieren. Ich würde es wirklich schätzen, wenn jemand den Grund erklären würde, warum mein Code nicht funktioniert und meine Lücken ausfülle.

Answer 1

Sie rufen undefiniertes Verhalten auf, indem Sie das Ende einer Funktion erreichen, die definiert wurde, um einen Wert zurückzugeben, ohne etwas zurückzugeben. Ihr Compiler sollte eine Warnung ausgegeben haben. Wenn dies nicht der Fall ist, sollten Sie Compiler-Warnungen aktivieren.

findprime gibt immer etwas int, aber wenn x durch einen der Werte in primes nicht teilbar ist, dann werden Sie das Ende der Funktion zu erreichen, ohne jemals begegnet eine return Aussage. Was soll es in diesem Fall zurückgeben? Die Antwort ist, dass die Antwort nicht spezifiziert ist. Die Implementierung kann in diesem Fall frei tun, was sie will. In diesem Fall scheint es nur x zurückzukehren.

Answer 2

Hier ist der gereinigt Code, mit den Fehlern kommentiert und Fixes [bitte unentgeltlichen Stil Bereinigungs verzeihen]:

#include <vector> 
#include <iostream> 
std::vector <int> primes; 

// NOTE/BUG: before this was returning the inverse sense 
// RETURNS: 0=not prime, 1=prime 
int 
findprime(int x) 
{ 
    for (int p = 0; p < primes.size(); ++p) { 
     if (x % primes[p] == 0) { 
      return 0; 
     } 
    } 

    // BUG: this return was missing 
    return 1; 
} 

int 
main() 
{ 
    primes.push_back(2); 

    for (int i = 3; i < 100; ++i) { 
     // BUG: before this was _always_ adding the number 
#if 0 
     primes.push_back(findprime(i)); 
#else 
     if (findprime(i)) 
      primes.push_back(i); 
#endif 
    } 

    for (int i = 0; i < primes.size(); ++i) { 
     std::cout << primes[i] << '\n'; 
    } 
} 

Answer 3

Yours und die Lösungen Verfasser sind unterschiedlich:

Autor Logik ist zu prüfen, Primalität einiger Nummer n. Dies geschieht dadurch, dass früh beendet wird, wenn eine Primzahl n gleichmäßig teilt, und erst nach Überprüfung aller Primzahlen, die true ergeben.

Was Ihr Code int findprime (int x) tut, ist dies nicht. Es gibt x zurück, wenn x nicht mindestens eine vorhandene Primzahl gleichmäßig aufgeteilt werden kann. Da es kategorisch jede Zahl als Primzahl hinzufügt, kann es immer eine Nummer finden, die x nicht perfekt teilen kann. Und wie andere erwähnt haben, ist die Funktion schlecht geschrieben, weil sie so verzweigen kann, dass alle return Anweisungen vermieden werden (schlecht, führt zu undefiniertem Verhalten).

Ich schlage vor, die Version des Autors zu verwenden und zu studieren, warum es funktioniert - es funktioniert, weil, wenn es früh verlässt, es mit Sicherheit tut. Nicht in der Lage zu sein, durch eine Prime geteilt werden, ist nicht garantiert, dass Sie mit einem Prime beschäftigen, es ist, wenn alle Primzahlen nicht teilen Sie Ihre Nummer - ergo wenn kann teilen kann dann die Nummer ist nicht Prime und keine Notwendigkeit zu überprüfe weiter. Es gibt fortgeschrittenere Tests, aber Primzahltests und das Finden von Primzahlen sind ein eigenes Thema, das über die Spezifika jeder Programmiersprache oder Methode hinaus erforscht werden kann.

Answer 4

sollten Dieser Code funktioniert:

int findprime(int x) 
{ 
    for (int p=0; p<primes.size(); p++) 
    { 
     if ((x%primes[p])==0) 
     { 
      return -1; 
      break; 
     } 
    } 
return x; 
} 

int main() 
{ 
    primes.push_back(2); 
    primes.push_back(3); 
    for (int i=3; i<100; ++i) 
    { 
     if(findprime(i)!=-1) 
     { 
     primes.push_back(i); 
     } 
    } 
    for (int i=0; i<primes.size(); ++i) 
    { 
     cout << primes[i] << '\n'; 
    } 
} 

Wie in einer der Antwort es oben beschrieben ist. Sie durchlaufen alle Werte von Vektoren und geben am Ende nichts zurück.