c - 如何使用递归计算并打印前 N 个素数

Question

我编写了以下递归代码，但结果很奇怪。请帮忙找出我的 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);
    }
}

检查 Number 是否为质数的函数:

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
}

输出:[如果 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。

Answer 1

问题是您使用静态变量i作为除数，该变量永远不会重置为2来测试下一个数字。

这是 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");
}