Rekursive Primzahl Funktion C++

Question

Ich versuche zu verstehen, wie rekursive Funktionen zu verwenden, und ich verstehe nicht, warum diese Funktion falsch ist. Ich glaube, es ist in Base Case 2, aber ich weiß nicht warum.

#include <iostream> 
using namespace std; 

// Returns 0 if value is not prime, 1 if value is prime 
int IsPrime(int testVal, int divVal) 
{ 
    // Base case 1: 0 and 1 are not prime, testVal is not prime 
    if(testVal == 0 || testVal == 1){ 
     return 0; 
    } 
    // Base case 2: testVal only divisible by 1, testVal is prime 
    if(testVal/1 == testVal){ 
     return 1; 
    } 
    // Recursive Case 
     // Check if testVal can be evenly divided by divVal 
     // Hint: use the % operator 
     if(testVal % divVal != 1){ 
     IsPrime(testVal, divVal); 
     } 
     // If not, recursive call to isPrime with testVal and (divVal - 1) 
    return 0; 
} 

int main(){ 
    int primeCheckVal = 0; // Value checked for prime 

    // Check primes for values 1 to 10 
    for (primeCheckVal = 1; primeCheckVal <= 10; ++primeCheckVal) { 
     if (IsPrime(primeCheckVal, (primeCheckVal - 1)) == 1) { 
     cout << primeCheckVal << " is prime." << endl; 
     } 
     else { 
     cout << primeCheckVal << " is not prime." << endl; 
     } 
    } 
} 

Answer 1

testVal/1 == testVal ist immer true (vorausgesetzt, Sie sind nicht mit seltsamen Dingen wie Unendlichkeiten oder NaNs spielen) so wahrscheinlich nicht tut, was Sie erwarten (die Überprüfung, ob die Zahl nur teilbar durch ein) - Versuchen Sie es mit dem Prime 7 und dem Composite 15 und Sie werden sehen, dass es so ist.

daher eine beliebige Zahl von Null oder ein bis Ihre Funktion übergeben wird fälschlicherweise als prime detektiert werden.

Um zu sehen, ob eine Zahl durch eine nur teilbar ist, müssen Sie prüfen, ob er von einem anderen Kandidatenwert nicht teilbar ist. Als Beispiel (Pseudocode):

def isPrime(n): 
    testVal = 2 
    while testVal * testVal <= n: 
     if int (n/testVal) * testVal == n: 
      return false 
    return true 

---

Als Nebenwirkung, ich bin nicht ganz davon überzeugt, dass primality getestet, um eine rekursive Lösung geeignet ist. Sie können entweder eine nicht-rekursive Lösung (wenn Ihr Ziel Primzahlen erkennen soll) oder ein anderes Problem (wenn Sie Rekursion lernen wollen) betrachten.