Prime number (Recursive method) in C++

Question

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

You made a similar code in python but your question is about c++. Unless you edit the question and provide the code, why add a python tag — , Aug 01 '21 at 02:49
`return isPrime(num, count, div++);` will increment `div` but essentially the same as writing `return isPrime(num, count, div);`. So, your code suffers from infinite recursion. You probably need `++div`. — Ruks, Aug 01 '21 at 02:51
RIght, to spoil the surprise, you need either `++div` or (more sensibly) `div+1`. BTW< you would have found this immediately if you had taken the obvious debugging step of printing the three parameters as the first line of your function. — Tim Roberts, Aug 01 '21 at 02:52
I hope you understand that this is a terrible way to check for primes. It doesn't gain anything by being recursive, and you don't have to check any numbers past `sqrt(num)`. — Tim Roberts, Aug 01 '21 at 02:55
@TimRoberts haha, literally i know that but that's the only way i know how to find if a number is prime. BTW looking for solutions i saw that some people use sqrt(num) but i dont understand the logic behind that method of finding prime numbers. Could you please explain to me that method?. — Sergio2405, Aug 01 '21 at 03:45
If a number has any factors (except 1 and itself), then at least one of them has to be below sqrt(n). Right? If there are factors (other than sqrt(n)), then there must be a pair of them: one below sqrt(n) and one above sqrt(n). So, you just look from 2 to sqrt(n), and if you find no factors, the number is prime. — Tim Roberts, Aug 01 '21 at 04:57

Ruks · Accepted Answer · 2021-08-01T03:14:51.610

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:

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

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

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

Yeah, that was the problem! Now it works fine. Thank you!. Also that's the only way i know how to find prime numbers. Can you explain to me the method you're using, please. — Sergio2405, Aug 01 '21 at 03:42
Tip: A much _faster_ loop is `for (int i = 2; i <= num / i; ++i)`. Changes from O(n) to ( sqrt(n))` — chux - Reinstate Monica, Aug 01 '21 at 03:48

score 0 · Answer 2 · answered Aug 01 '21 at 03:18

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

Prime number (Recursive method) in C++

2 Answers2