рекурсивно проверить, является ли число простым числом

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.

Пожалуйста, помогите мне понять, что я делаю не так.

Answer 1

Вы не вызываете рекурсивную функцию. return (n,d-1); должно быть return isPrime(n,d-1);

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

Пожалуйста, не пишите это так! Для более или менее нормального ввода рекурсивный подход уничтожит весь стек! Просто иди по старому доброму итеративному пути.

Конечно, решение о грубой силе не самое быстрое. Вы можете попробовать сито Эратосфена или некоторые из многочисленных более сложных тестов .

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