递归检查数字是否为质数

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的数字，即n-1。

请帮我找出我做错了什么。

- Marijus

Answer 1

你的函数没有进行递归调用。return (n,d-1); 应该改为 return isPrime(n,d-1);

- GWW

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);
    }
}

- Shubham Godara

Answer 3

请不要这样写！对于更或多或少正常的输入，递归方法会耗尽所有堆栈！最好采取老式的迭代方式。

当然，暴力解决方案并不是最快的。您可以尝试Eratosthenes筛法，或者一些众多的高级测试。

- Vlad

---

是的，我知道這只能處理小數字，但我只是為了學習遞歸而這麼做。 - Marijus

任何理智的编译器都会将尾递归优化为迭代。 - fredoverflow

@Fred: 我不会依赖这个，除非这是由标准保证的。 - Vlad

标准并不保证任何优化，但我们仍然更喜欢C++而不是手写汇编。 - fredoverflow

@Fred：不行。你认为调试版本崩溃是可以接受的吗？ - Vlad

Answer 4

#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);
}
}

- Baivab Dash