CODEWITHSUNDEEP
c++recursion
Sergio2405
Sergio2405

Reputation: 61

Prime number (Recursive method) in C++

i made this code to find if a positive integer n is prime or not. But it doesnt work (we i run it, it doesnt return anything). I have a similar code for python and that works fine but this one in c++ it doesnt, i dont know why.

#include <iostream>

bool isPrime(int num, int count=0, int div =1) {
  if (div>num){
    if (count==2){
      return true;
    }else{
      return false;
    }
  }else{
      if (num % div ==0){
        count ++;
      }
      return isPrime(num, count, div++);
    }
}

int main(){ 
    
    int n;
    std::cin >> n;
    std::cout << isPrime(n);
    
    return 0;
}

Upvotes: 0

Views: 966

Answers (2)

yashsh
yashsh

Reputation: 79

Use ++div (previx operator) as a parametere inside of your isPrime function as you want to increment the value first and then recurse the function. This should work:

#include <iostream>

bool isPrime(int num, int count=0, int div =1) {
    if (div>num){
        if (count==2){
          return true;
        }else{
          return false;
        }
    }else{
      if (num % div ==0){
        count ++;
      }
      return isPrime(num, count, ++div);
    }
}

int main(){ 

    int n;
    std::cin >> n;
    std::cout << isPrime(n);

    return 0;
}

Upvotes: 0

Ruks
Ruks

Reputation: 3956

As already stated, the culprit is this line:

return isPrime(num, count, div++);

div++ is a post-increment operation, so the value is div is returned first and then div is incremented, which causes your function to go into infinite recursion because div will always remain 1 in all recursive calls to isPrime(...).

You can fix that by doing any one of these three things:

  1. div++; // Take the post-increment outside the function call
return isPrime(num, count, div);

  2. // Using pre-increment
return isPrime(num, count, ++div);

  3. // Using normal arithmetic addition
return isPrime(num, count, div + 1);

Also, a better way to check for prime numbers is by using a for-loop:

bool isPrime(int const num) {
    if (num <= 1) return 0;
    for (int i = 2; i < num / 2; ++i)
        if (num % i == 0)
            return 0;
    return 1;
}

Upvotes: 2

Related Questions