在c语言中使用只有一个参数的递归检查数字是否为质数

Question

我的课程中有一个任务是编写一个函数来检查一个数是否为素数，如果是，它将 return 1，如果不是，则为 0，所有这些都要做递归地。该函数将如下所示：int isPrime(int num); 我已经尝试了所有方法并到处搜索，得出的结论是，只有使用我还没有学过的 static int 才有可能，所以不能使用它或使用两个参数。有谁知道是否有一种方法可以只用一个参数而不用静态整数来解决它？谢谢。

Answer 1

这是一个技巧问题：你应该使用递归，但除非你被禁止使用循环，否则可以使用 for 循环的经典解决方案来满足递归要求。

这是一个函数 isPrime，它只有一个参数并使用经典循环和递归来测试素因数：

int isPrime(int n) {
    if (n <= 1)
        return 0;
    if (n % 2 == 0)
        return n == 2;
    for (int p = 3; p * p <= n; p += 2) {
         if (isPrime(p) && n % p == 0)
             return 0;
    }
    return 1;
}

以上代码只对素数进行取模运算。这是一个错误的优化，因为通过递归调用确定 p 是否为质数实际上比计算 n % p.

的成本更高

Answer 2

所以这是我对这个有问题的作业的解决方案。它仅包含采用一个 int 参数并使用递归且没有循环的函数：

#include <iostream>
#include <functional>

std::function<bool(int)> isPrime(int x) {
    return [x](int p) {
        if (x <= 2) return true;
        return (p % (x - 1) != 0) && (isPrime(x - 1)(p));
    };
}

int main() {
    if (isPrime(19)(19)) std::cout << "is prime" << std::endl;
}

在c语言中使用只有一个参数的递归检查数字是否为质数

check if number is prime using recursion with only one parameter in c language

c

function

recursion

primes