英文:
How to calculate and print first N Prime Numbers Using Recursion
问题
我写了以下递归代码，但结果很奇怪。请帮忙找出我的 C 代码中的错误。
例如，如果我将 n 的值设为 10，那么输出应该是 2,3,5,7,11,13,17,19,23,29，但是我的代码输出是 2 3 5 7 9 11 13 15 17 19。
啊！我尝试了很长时间，但找不到问题。这是我的递归 C 代码：
void primeNumbers (int n)
{
if (n == 0)
return;
static int i = 2;
if (isPrime(i))
{
printf("%d ", i);
i++;
primeNumbers(n - 1);
}
else
{
i++;
primeNumbers(n);
}
}
检查数字是否为素数的函数：
bool isPrime(int n)
{
// 边缘情况，不是基本情况
if (n <= 1)
return false;
static int i = 2;
if (i > n / 2)
return true;
if (n % i == 0)
return false;
i++;
return isPrime(n); // 用 i+1 的值再次调用
}
输出：[如果 N 为 10]
2 3 5 7 9 11 13 15 17 19
如果我将 n 的值设为 10，那么输出应该是 2,3,5,7,11,13,17,19,23,29，但是我的代码输出是 2 3 5 7 9 11 13 15 17 19。
英文:
I wrote the following recursive code but the outcome is strange. Please Help to find the error in my C code.
For example if I take the value of n as 10 then the output should be 2,3,5,7,11,13,17,19,23,29
but with to my code the output is 2 3 5 7 9 11 13 15 17 19
Ahh! I tried for a long time but couldn't find the problem. Here is my recursive C code:
void primeNumbers (int n)
{
if (n == 0)
return;
static int i = 2;
if (isPrime(i))
{
printf("%d ", i);
i++;
primeNumbers(n - 1);
}
else
{
i++;
primeNumbers(n);
}
}
The function to check Number is Prime or not:
bool isPrime(int n)
{
// edge case, not a base case
if (n <= 1)
return false;
static int i = 2;
if (i > n / 2)
return true;
if (n % i == 0)
return false;
i++;
return isPrime(n); // call again with i+1 value
}
Output: [if N is 10]
2 3 5 7 9 11 13 15 17 19
if I take the value of n as 10 then the output should be 2,3,5,7,11,13,17,19,23,29 but with to my code the output is 2 3 5 7 9 11 13 15 17 19.
答案1
得分: 2
问题在于您使用一个永远不会重置为2的static变量i作为除数，用于测试下一个数字。
以下是isPrime的另一种递归实现：
bool testPrime(int n, int div) {
if (n / div < div)
return true;
else if (n % div == 0)
return false;
else
return testPrime(n, div + 1);
}
bool isPrime(int n) {
return n >= 2 && testPrime(n, 2);
}
递归函数可以简化为单个表达式：
bool testPrime(int n, int div) {
return (n / div < div) || (n % div != 0 && testPrime(n, div + 1));
}
由于相同的原因，枚举函数也是不正确的：static变量i从未重置为2，所以该函数只会工作一次，而且在测试和打印i后，您以n - 1的递归方式调用它，因此它会在中途停止。
对于primeNumbers()，可以采用相同的方法将循环转换为递归调用：
void printPrimes(int p, int n) {
if (n > 0) {
if (isPrime(p)) {
printf("%d ", p);
printPrimes(p + 1, n - 1);
} else {
printPrimes(p + 1, n);
}
}
}
void primeNumbers(int n) {
printPrimes(2, n);
printf("\n");
}
英文:
The problem is you use a static variable i for the divisor that never gets reset to 2 for the next number to test.
Here is an alternative recursive implementation of isPrime:
bool testPrime(int n, int div) {
if (n / div < div)
return true;
else
if (n % div == 0)
return false;
else
return testPrime(n, div + 1);
}
bool isPrime(int n) {
return n >= 2 && testPrime(n, 2);
}
The recursive function can be simplified as a single expression:
bool testPrime(int n, int div) {
return (n / div < div) || (n % div != 0 && testPrime(n, div + 1));
}
The enumerating function is also incorrect for the same reason: static variable i is never reset to 2 so the function would only work once, and you call it recursively with n - 1 after testing and printing i so it stops enumerating half way.
The same approach can be taken for primeNumbers() to convert a loop into recursive calls:
void printPrimes(int p, int n) {
if (n > 0) {
if (isPrime(p)) {
printf("%d ", p);
printPrimes(p + 1, n - 1);
} else {
printPrimes(p + 1, n);
}
}
}
void primeNumbers(int n) {
printPrimes(2, n);
printf("\n");
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论