Finding the smallest prime factor using recursion c++

Question

I am new to c++ and I have been tasked to write a code which finds the smallest prime factor of a number using recursion. If N is less than 2 the code should return 1. If N is a prime number itself the code should return N. Otherwise the code should return the smallest prime factor of N. I have attempted the question but I have used a for loop to check for the lowest prime factor and I am unsure if this method in the context of my answer is iterative or recursive. To call the function for main the user should enter lowestPrimeFactor(x);, where x is the number they want to find the lowest prime factor for. I am stuck with trying to change the iterative section to recursive, where the code checks for the lowest prime factor. I would appreciate any feedback.

#include <stdio.h>
#include <iostream>
#include <math.h>
long lowestPrimeFactor(long N, long i=2) {
    if(N<2){  //if N is less than 2, return 1
        std::cout << 1; //print to screen to check
        return 1;
    }

    bool isPrime =true; //Check if number is prime
    for(i=2;i<=N/2; ++i){
        if(N%i==0){
            isPrime=false;
            break;
        }
    }
        if (isPrime){
            std::cout<<N;
            return N;
        }

        for (int i = 3; i* i <= N; i+=2){ //This is where I am unsure how to translate to recursive as it is based of an iterative solution
                if(N%i == 0)
                std::cout<<i;
                return i;
    }


//Driver code to check functionality
int main(){
lowestPrimeFactor(19);
}

EDIT I think I have modified the code correctly to be recursive for the prime factor check

        //Recursive
        if(i*i<=N){
            N%i==0; lowestPrimeFactor(i);
        }
        else return i;

Just need to try and adjust the bool part to be recursive too

Answer 1

The required code, if you want to use recursion for checking out the lowest prime factor instead of the last for loop would be as follows:

#include <iostream>

long lowestPrimeFactor(long N,long pr = 3)
{
bool isPrime =true;
if(N<2)
{  //if N is less than 2, return 1
    std::cout << N << std::endl;//print to screen to check
    return 1;
}    
else
{
    for(long i=2;i<=N/2; ++i)
    {
        if(N%i==0)
        {
        isPrime=false;
        break;
        }
    }
}
if(isPrime)
{
    std::cout << N << std::endl;
    return N;
}
else
{
    if(N%2==0){
        std::cout << 2 << std::endl;
        return 2;
    }
    else
    {
        if(N%pr == 0)
        {
            std::cout << pr << std::endl;
            return pr;
        }
        else
        {
            return lowestPrimeFactor(N,pr+2);
        }    
    }
}
}

//Driver code to check functionality
int main()
{
lowestPrimeFactor(19);
lowestPrimeFactor(20);
lowestPrimeFactor(7);
lowestPrimeFactor(1);
lowestPrimeFactor(15);
}

This isn't fully recursive but it checks for only prime numbers till 7 after which it checks for 9 and so on i.e odd numbers which even the original code had. Note: Prime factors it checks properly: 2,3,5,7 and prime numbers

Answer 2

Try this:

#include <iostream>

using namespace std;

long lowestPrimeFactor(long N, long i = 2) {
    if (N % i == 0) // Test for factor
        return i;
    else if (i < N * N)
        return lowestPrimeFactor(N, i + 1); // Test next factor
    else
        return N;
}

void test(long N){
    // Format results
    cout << N << " gives " << lowestPrimeFactor(N) << endl;
}

int main() {
    for (long N = 2; N < 30; ++N)  // Generate some test cases
        test(N);
}

This has the inefficiency that it tests for non-prime factors too (which I think the original solution also does) so really rather than recursing with i + 1 (the next integer after i) we should be calculating and passing in the next prime after i.