递归素数函数C++

我想了解如何使用递归函数，我不明白为什么这个函数是错误的。我相信它是在基本案例2中，但我不知道为什么。递归素数函数C++

#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; 
     } 
    } 
}

来源

2017-10-13 Maria Teleki

真的不清楚你试图用'if（testVal/1 == testVal）'来完成什么 - 它总是**是真的，因为除以1的所有东西都等于它自己。 – Steve

这听起来像您可能需要学习如何使用调试器来遍历代码。使用一个好的调试器，您可以逐行执行您的程序，并查看它与您期望的偏离的位置。如果你打算做任何编程，这是一个重要的工具。进一步阅读：[如何调试小程序]（http://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。这样做你会发现，不要修改'testVal'或'divVal' – NathanOliver

testVal/1 == testVal是总是真（前提是你不喜欢无穷大或NaN怪异的东西弹），所以可能不会做你所期望的（检查如果数字是只有整除之一） - 使用主要的7和复合15来尝试，你会发现它是如此。

因此，任何传递到您的函数的零或一个数字将被错误地检测为素数。

要查看一个数字是否只能被一个整除，您需要检查它是否不能被任何其他候选值整除。通过举例的方式（伪代码）：

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

顺便说一句，我并不完全确信，素性测试是适合于递归溶液。您可能想要查看非递归解决方案（如果您的目标是检测素数）或不同的问题（如果您的目标是学习递归）。

来源

2017-10-13 13:46:40 paxdiablo

递归素数函数C++

回答

相关问题