c - 如何在C中使用递归查找素数

Question

我正在编写一个程序，使用递归在 C 中查找素数。这是我写的程序。

#include<stdio.h>
#include<conio.h>

void rec(int, int);
int main()
{
    rec(2,2);
    getch();
    return 0;
}
void rec(int n, int x)
{
    if(x>999)
        return;
    if(n==x)
    {
        printf("%d ,", x);
        rec(2,x+1);
        return;
    }
    if(x%n==0)
    {
        rec(2,x+1);
        return;
    }
    rec(n+1,x);
}

我不知道它出了什么问题，它一直运行良好，直到 887 之后崩溃。要进行检查，只需将 x>999 替换为 x>300，它就可以工作，但不适用于 x>999。请指出程序中的错误，而不是编写一个全新的程序。

Answer 1

可能超出了递归深度。

递归深度似乎与限制的平方成正比。
尝试一下

#include <stdio.h>
int depth = 0;
int maxdepth = 0;

void rec(int n, int x) {
  depth++;
  if (depth > maxdepth) maxdepth = depth;
  if (x > 860) {
    depth--;
    return;
  }
  if (n == x) {
    printf("%d ,", x);
    rec(2, x + 1);
    depth--;
    return;
  }
  if (x % n == 0) {
    rec(2, x + 1);
    depth--;
    return;
  }
  rec(n + 1, x);
  depth--;
}

int main(void) {
  rec(2, 2);
  printf("\n depth %d maxdepth %d\n", depth, maxdepth);
  return 0;
}

最大深度 60099(限制为 860)

代码需要一种深度不那么密集的方法。

尝试将 n 除以 2 到 sqrt(n) 的所有素数。如果数量为偶数，则它仅是 2 的素数。否则，如果低于 7，则如果不是 1，则它是素数。否则要找到大于 7 的素数，将 2 添加到前一个素数候选中，并递归测试它是否是素数。因此，您有两个函数 bool is_prime(n) 和 unsigned next_prime(n) 相互调用。

最大深度:3(所有 1000)

喜欢OP的self description ，在这种情况下“并且懒得进一步透露任何内容。”