递归检查数字是否为素数

Question

我正在尝试检查该数字是否是质数（通过将其除以 n 以下的所有数字）。这是我的尝试：

bool isPrime(int n, int d){
    if (d == 1)
        return true;
    else{
        if (n % d == 0){
            return false;
        }
        else
            return (n,d-1);
    }
}

n - 检查它是否是素数的数字。 d - 当调用函数 n-1 时，n 以下的数字。

请帮我弄清楚我做错了什么。

Answer 1

请不要这样写！对于或多或少的正常输入，递归方法将吃掉所有堆栈！只需采用旧的迭代方式即可。

当然，暴力解决方案并不是最快的解决方案。您可以尝试Eratosthenes' sieve，或众多更高级的测试。

Answer 2

您只需要添加检查 1 是否为素数的条件即可。

bool isPrime(int n, int d)
{
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

Answer 3

#include<iostream>
using namespace std;
bool findPrime(int x,int y);
int main()
{int n;
cout<<"enter the number to be checked \n";
cin>>n;
  int x=findPrime(n,n-1);
  if(x==1)
    cout<<"its a prime number";
  else
    cout<<"its not prime";
}
bool findPrime(int x,int y)
{
    if(x%y==0&&y!=1)
    {
        return false;
        }
    else{
        if(y==1)
        return true;
    else
        return findPrime(x,y-1);
}
}

Answer 4

您没有递归调用您的函数。 return (n,d-1); 应该是 return isPrime(n,d-1);