c - 用 C 语言编写一个程序，使用递归来确定数字是否为素数。当数字很大时出现堆栈溢出错误

Question

用 C 语言编写一个程序，使用递归来确定一个数是否为素数。它一直有效，直到您尝试使用 9431 以上的质数。任何高于该值的数字都会出现堆栈溢出错误。我想知道是否有办法解决这个问题。

除了查看失败的次数(每次都不同)之外，我还没有真正尝试过任何其他操作。

//Remove scanf error
#define _CRT_SECURE_NO_WARNINGS

//Preprocessor directives
#include<stdio.h>
#include<stdlib.h>

//Recursion function
int PrimeCheck(int choice, int i)
{
    //Check if integer i is reduced to 1
    if (i == 1)
    {
        return 0;
    }
    else
    {
        //Check to see if number choice is divisible by value i
        if (choice % i == 0)
        {
            return 1;
        }

        //Call the function again but reduce the second variable by 1
        else
        {
            return PrimeCheck(choice, i - 1);
        }
    }
}//End PrimeCheck function

//Main function
main()
{
    //Assign needed variables
    int choice, num;

    //ask for user input
    printf("Please enter a number between 2 and %i:", INT_MAX);
    scanf("%i", &choice);

    //Check for numbers outside the range
    if (choice < 2 || choice > INT_MAX)
    {
        printf("Please try again and enter a valid number.\n");
        system("pause");
        return 0;
    }

    //Call the PrimeCheck "looping" function
    num = PrimeCheck(choice, choice / 2);

    //Display result for the user
    if (num == 0)
    {
        printf("%i is a prime number.\n", choice);
    }

    else
    {
        printf("%i is NOT a prime number.\n", choice);
    }

    system("pause");
}//End main

输出应该是“____是素数”或“____不是素数” 9431以上的实际输出是堆栈溢出错误。

Answer 1

一个帮助，减少测试。

PrimeCheck(choice, choice / 2);迭代 choice/2有时只有 sqrt(choice)需要的时间。

而不是从 choice/2 开始

PrimeCheck(choice, sqrt(choice));

更好的代码可以避免小舍入误差和整数截断

PrimeCheck(choice, lround(sqrt(choice)));

或者如果您可以使用整数平方根函数:

PrimeCheck(choice, isqrt(choice));

对于9431 ，这会将堆栈深度减少约 50 倍 - 并加快程序速度。

<小时/>

速度性能提示。而不是从 choice / 2 迭代或sqrt(choice) 向下到 1。向上从 2 到 sqrt(choice) 。非质数将被更快地检测到。

<小时/>

示例

#include <stdbool.h>
#include <stdio.h>

bool isprimeR_helper(unsigned test, unsigned x) {
  // test values too large, we are done
  if (test > x/test ) {
    return true;
  }
  if (x%test == 0) {
    return false; // composite
  }
  return isprimeR_helper(test + 2, x);
}

bool isprimeR(unsigned x) {
  // Handle small values
  if (x <= 3) {
    return x >= 2;
  }
  // Handle other even values
  if (x %2 == 0) {
    return false;
  }
  return isprimeR_helper(3, x);
}

int main(void) {
  for (unsigned i = 0; i < 50000; i++) {
    if (isprimeR(i)) {
      printf(" %u", i);
    }
  }
  printf("\n");
}

输出

2 3 5 7 11 13 17 19 ... 49991 49993 49999

<小时/>

实现说明

请勿使用if (test*test > x) 。使用test > x/test

• test*test可能会溢出。 x/test不会。

• 好的编译器会看到附近的 x/test和x%test并将两者作为一项操作进行有效计算。因此，如果代码有 x%test ，成本x/test如果通常可以忽略不计。