用 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的成本通常可以忽略不计。