Как расшифровать Exit code?

Question

[Marty1337]

Решаю задачу с проекта Эйлера, столкнулся с такой проблемой:
Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?

# Каков самый большой делитель числа 600851475143, являющийся простым числом?
import sys
sys.setrecursionlimit(2**20)
d = 2
n = 1241452
def main():

    ar = []

    def delit(d):
        global a
        global n
        if n % d == 0:
            ar.append(d)
            n = n/d
            if n == 1:
                print(ar)
            else:
                delit(2)
        else:
            a = simp_ind(d)


    def simp_ind(d):
        p = 2
        d +=1
        while d % p != 0:
            p += 1
        if p == d:
            delit(d)
        else: simp_ind(d)

    delit(d)

if __name__ == '__main__':
    main()

До числа n = 1241451 Задачу решает, если число больше, выдает ошибку:

Process finished with exit code -1073741571 (0xC00000FD)

Comments

[mayton2019]

Поставь себе утилитку фактор. Чтоб проверять.

$ factor 600851475143
600851475143: 71 839 1471 6857

Ну и рекурсию надо "размотать". А то она слишком "замотана". Замоталась...

Answer 1

[Сергей Горностаев]

Переполнение стека.

Answer 2

[Сергей П]

Вы поставили ограничение глубины стека таким большим, что память заканчивается задолго до достижения этого лимита, поэтому ваш процесс интерпретатора падает не показывая валидную ошибку.
Не стоит делать такой неадекватный лимит стека, тогда ваш интерпретатор упадёт с другой ошибкой - превышен лимит рекурсивных вызовов.
А уж эту проблему решать надо оптимизацией алгоритма. Ваш слишком жаден до стека.

Comments

[Marty1337]

Спасибо, хотелось просто ради эксперимента заставить работать программу так, ну да ладно

[Marty1337]

Изменил программу для нахождения простых чисел (для начала) вроде не зацикливается, но все равно выдает ошибку

RecursionError: maximum recursion depth exceeded in comparison

# Каков самый большой делитель числа 600851475143, являющийся простым числом?
import sys
#sys.setrecursionlimit(2**30)
d = 1
n = 1241452
def main():

    ar = []
    simp = []
    # def delit(d):
    #     global a
    #     global n
    #     if n % d == 0:
    #         ar.append(d)
    #         n = n/d
    #         if n == 1:
    #             print(ar)
    #         else:
    #             delit(2)
    #     else:
    #         a = simp_ind(d)


    def simp_ind(d):
        for i in range(10):
            p = 2
            d +=1
            while d % p != 0:
                p += 1
            if p == d:
                simp.append(d)
            else: simp_ind(d)

    simp_ind(d)
    print(simp)
if __name__ == '__main__':
    main()

[Сергей П]

Marty1337, потому что плохо реализовали.
Любую рекурсию можно заменить итеративным алгоритмом со стеком в качестве которого можно использовать тот же список.
В таком случае в стеке у вас будет лежать не весь контекст функуии, а только одно значение. Это более экономно.
Попробуйте описать алгоритм на человеческом и математическом языке, а потом уже беритесь писать программу. Складывается ощущение, что вы её пишете методом проб и ошибок.
Прочитайте что такое "чистые функции" и что такое "побочный эффект" в этом контексте. Старайтесь писать чистые функции.
Рекурсия в задачах вроде этой очень неэкономична. тем более, если вы ее не пытаетесь оптимизировать и экономично использовать стек.
Нужно пользоваться встроенными питоновскими структурами данных вроде словарей, которые позволяют получать значение по ключу за ~O(1). На этом можно построить много оптимизаций

[Сергей П]

Marty1337, любая рекурсия должна иметь критерий остановки. Иначе это не рекурсия, а ошибка.
Зачем проверять делимость на каждое число? Все четные можно исключить кроме 2, все кратные 3 кроме 3 и т.д. Вы же решаете задачу очень неэффективно.

[Marty1337]

Сергей Паньков, Спасибо большое за ответ, буду разбираться

Answer 3

[Telcontar]

Слишком большое число :)

Comments

[Marty1337]

Ну неужели intel core i7 не может решить данную задачу?)

[Сергей Горностаев]

Marty1337, причём тут модель процессора? Размер стека python-приложения от процессора не зависит.

[Roman K]

Marty1337, купи i9, может на нём решишь задачу