如何使用递归在 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 加到先前的素数候选中，并递归地测试它是否是素数。所以你有 2 个函数 bool is_prime(n) 和 unsigned next_prime(n) 互相调用。

最大深度：所有 1000 个都为 3

就像 OP 的 self description，在这种情况下 "And too lazy to tell anything further."

Answer 2

#include<stdio.h>

void rec(int test_number, int prime_index);

int main(void){
    rec(2, 0);

    return 0;
}

void rec(int n, int i){
    static int prime[500], cp;//for memorize
    if(n > 999)
        return;
    if(prime[i] == 0 || prime[i]*prime[i] > n){//prime[i]*prime[i] > n : To reduce the depth of recursion by narrowing the upper limit of the test.
        printf("%d, ", n);
        prime[cp++] = n;
        rec(n + 1 + (n != 2), 0);//n != 2 : Avoid an even number of other than 2
        return;
    }
    if(n % prime[i]==0){
        rec(n + 1 + (n != 2), 0);
        return;
    }
    rec(n, i+1);
}

Answer 3

您可以尝试使用以下代码查找 1 和给定整数 N（范围内的素数列表）之间的素数：

#include<stdio.h>
void main()
{
    int n,flag=0,i,j;
    printf("Enter range of prime number : ");
    scanf("%d",&n);
    printf("\nPrime numbers are : ");
    for(i=1;i<n;i++)
    {
        flag=0;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                flag=1;
                break;
            }
            else
                flag=0;
        }
        if(flag==0)
            printf("\n%d",i);
    }
}

Answer 4

问题： rec 函数在不同条件语句下多次递归导致递归深度增加。

解决方案： 减少 rec 函数在条件语句下的使用，方法是在 main 函数中有一个循环以在 rec函数。

#include<stdio.h>
void rec(int,int);
int main()
{
    int i=2;
    while(i<=1000) //passing 2,3,4...,1000 (one by one) in rec function to check if it is prime or not
    {
        rec(2,i);
        i++;
    }
}
void rec(int n,int x)
{
    if(n==x) //if number(n) by which divisibility is checked and number(x or i) which is under checking gets equal then number(x or i) is proved as prime and get printed
        printf("%d, ", x);
    else if(x%n!=0) //if number(x or i) under checking is not divisible by number(n) then call rec function again to check divisibility of number(x) by number(n+1)
        rec(n+1,x);
//if number(x or i) under checking is divisible by number(n) at any stage then return to main function and next number(i++ or new x) is passed to rec function to check if it is prime or not
}

建议：递归函数很有趣。但是使用递归函数或任何简单方法将素数打印到像 (10^6) 这样的大极限非常慢。使用 Eratosthenes 筛法（快速、简单且有趣）或它的某些 修改版本（最快） 可以非常快速地打印出任意范围的素数。还尝试学习 Sundaram 筛法（它也很慢但很有趣）和 阿特金筛法（快速且有趣但复杂）。

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

How to find prime numbers in C using recursion

c

stack-overflow

crash

recursion

primes