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

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

2 голосов
/ 30 января 2012

написал код для того, что я считаю хорошим алгоритмом для нахождения наибольшего простого множителя для большого числа с использованием рекурсии.Моя программа аварийно завершает работу с любым числом, больше 4, назначенным переменной global_number.Я плохо разбираюсь в рекурсии, и присваивание не допускает какого-либо цикла.

#include <stdio.h>

long long prime_factor(int n, long long huge_number);

int main (void)
{
    int n = 2;
    long long huge_number =  60085147514;
    long long largest_prime = 0;

    largest_prime = prime_factor(n, huge_number);
    printf("%ld\n", largest_prime);

    return 0;
}

long long prime_factor (int n, long long huge_number)
{
    if (huge_number / n == 1)
        return huge_number;
    else if (huge_number % n == 0)
        return prime_factor (n, huge_number / n);        
    else
        return prime_factor (n++, huge_number);
}

любая информация о том, почему происходит сбой и как я могу его улучшить, будет принята с благодарностью.

Ответы [ 4 ]

1 голос
/ 30 января 2012

Вы переполняете стек, потому что n ++ постинкрементно увеличивает значение, делая рекурсивный вызов с теми же значениями, что и в текущем вызове.

1 голос
/ 30 января 2012

Вы имели в виду n+1 вместо n++. n++ увеличивает n после использования , поэтому рекурсивный вызов получает исходное значение n.

0 голосов
/ 30 января 2012

причина сбоя - переполнение стека. Я добавляю счетчик в вашу программу и запускаю его (в Ubuntu 10.04 GCC 4.4.3), где счетчик останавливается на «218287» перед дампом ядра. лучшее решение - использовать цикл вместо рекурсии.

0 голосов
/ 30 января 2012

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

Хотя ваше деление huge_number довольно быстро сокращает его, подавляющее большинство рекурсивных вызовов выполняется простым увеличением n. Это означает, что вы собираетесь использовать лот стекового пространства.

Вам было бы лучше либо:

  • использование итеративного решения, при котором вы не выбросите стек (если вы просто хотите решить проблему) (a) ; или
  • поиск более подходящей задачи для рекурсии, если вы просто пытаетесь изучить рекурсию.

(a) Примером такого зверя, смоделированного на вашем рекурсивном решении, является: 

#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
    while (n < huge_number) {
        if (huge_number % n == 0) {
            huge_number /= n;
            continue;
        }
        n++;
    }
    return huge_number;
}

int main (void) {
    int n = 2;
    long long huge_number =  60085147514LL;
    long long largest_prime = 0;

    largest_prime = prime_factor_i (n, huge_number);
    printf ("%lld\n", largest_prime);

    return 0;
}

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

Если вы действительно должны использовать рекурсивное решение, вы можете уменьшить пространство стека до квадратного корня из этого, используя тот факт, что у вас нет , чтобы проверить все вплоть до числа, но только до его квадратного корня.

Кроме того, кроме 2, все остальные простые числа нечетные, поэтому вы можете дополнительно сократить пространство поиска вдвое, проверив только два плюс нечетные числа.

Рекурсивное решение, учитывающее эти две вещи: 

long long prime_factor_r (int n, long long huge_number) {
    // Debug code for level checking.

    // static int i = 0;
    // printf ("recursion level = %d\n", ++i);

    // Only check up to square root.

    if (n * n >= huge_number)
        return huge_number;

    // If it's a factor, reduce the number and try again.

    if (huge_number % n == 0)
        return prime_factor_r (n, huge_number / n);

    // Select next "candidate" prime to check against, 2 -> 3,
    //   2n+1 -> 2n+3 for all n >= 1.

    if (n == 2)
        return prime_factor_r (3, huge_number);

    return prime_factor_r (n + 2, huge_number);
}

Вы можете видеть, что я также удалил (неудобно, на мой взгляд) конструкцию: 

if something then
    return something
else
    return something else

Я предпочитаю менее массивный код с отступом, который исходит от: 

if something then
    return something
return something else

Но это всего лишь личные предпочтения. В любом случае, это снижает уровень рекурсии до 1662 (раскомментируйте отладочный код для проверки), а не до десяти миллионов, что является значительным сокращением, но все же не идеальным. Это нормально работает в моей среде.

...