用 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

输出应该是“____ is a prime number”或者“____ is NOT a prime number” 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) down 迭代到 1。从 2 到 up 到 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 的成本通常可以忽略不计。

用 C 编写程序，使用递归来确定数字是否为质数。在高数字时出现堆栈溢出错误

Writing a program in C that uses recursion to determine if a number is prime or not. Getting a stack overflow error at high numbers

c

stack-overflow

recursion