Нахождение наименьшего простого множителя с помощью рекурсии c ++

Question

Я новичок в c ++, и мне было поручено написать код, который находит наименьший простой множитель числа с помощью рекурсии. Если N меньше 2, код должен возвращать 1. Если N само простое число, код должен возвращать N. В противном случае код должен возвращать наименьшее простое число из N. Я пытался задать вопрос, но я использовал a для l oop для проверки наименьшего простого множителя, и я не уверен, является ли этот метод в контексте моего ответа итеративным или рекурсивным. Чтобы вызвать функцию main, пользователь должен ввести lowerPrimeFactor (x); где x - это число, для которого он хочет найти наименьший простой множитель. Я застрял при попытке изменить итеративный раздел на рекурсивный, где код проверяет наименьший простой множитель. Буду признателен за любые отзывы.

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

РЕДАКТИРОВАТЬ Я думаю, что я изменил код правильно, чтобы быть рекурсивным для проверки простого фактора

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

Просто нужно попробовать и настроить часть bool быть слишком рекурсивным

Answer 1

Необходимый код, если вы хотите использовать рекурсию для проверки наименьшего простого множителя вместо последнего для l oop, будет выглядеть следующим образом:

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

Это не полностью рекурсивно, но он проверяет только простые числа до 7, после чего проверяет 9 и т. д., то есть нечетные числа, которые имел даже исходный код. Примечание: простые множители проверяются правильно: 2,3,5,7 и простые числа

Answer 2

Попробуйте это:

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

Это имеет ту неэффективность, что он проверяет и на непростые факторы (что я думаю, что оригинальное решение также делает), так что действительно, а не повторение с i + 1 (следующий целое число после i) мы должны вычислить и передать следующее простое число после i.