不带 while、do-while 或 for 循环的质数？

Question

帮助我：

编写一个不使用 do while、while 或 for 循环的 C 程序。该计划将
输入用户提供的 2 到 INT_MAX 之间的任意数字。程序将输出 if
输入的数字是 PRIME 或 NOT PRIME。

它还说“还有另一种方法可以在 C、Java、C++ 和其他程序中执行循环”

想不通

对于常见的循环来说，质数检测似乎很简单，但如果没有任何循环，我不知道从哪里开始。

Answer 1

您可以使用递归来计算数字的所有除数。如果除数计数等于 2，则该数字是质数。

int count_divisors(
    int dividend,
    int start_divisor
) {
    if(start_divisor > dividend) {
        return 0;
    }
    return (dividend % start_divisor == 0)
        + count_divisors(dividend, start_divisor + 1);
}

int is_prime(int number) {
    return count_divisors(number, 1) == 2;
}

神箭链接

Answer 2

可以使用递归来实现。创建一个函数来检查一个数字是否可以被给定范围内的任何数字整除。该函数将递归地调用自身以模仿循环的行为。

#include <stdio.h>
#include <limits.h>
#include <math.h>

int isPrime(int n, int i) {
    if (i > sqrt(n)) {
        return 1; 
    }
    if (n % i == 0) {
        return 0;
    }
    return isPrime(n, i + 1);
}

int main() {
    int n;
    printf("Enter a number between 2 and %d: ", INT_MAX);
    scanf("%d", &n);
    if (n < 2 || n > INT_MAX) {
        printf("Invalid input! Please enter a number between 2 and %d.\n", INT_MAX);
        return 1;
    }
    if (isPrime(n, 2)) {
        printf("PRIME\n");
    } else {
        printf("NOT PRIME\n");
    }
    return 0;
}