Что не так с моей рекурсией для поиска простых чисел? (Python)

Question

Я пытаюсь создать программу, которая перечисляет все простые числа под введенным числом, и я придумал код:

def primes():
    num = 20

    numlist = list(range(1,num+1))
    i = len(numlist)

    for j in numlist[2:]:
        ans = divisible(j,i)

        if ans:
            numlist.remove(j)
            print(numlist)

def divisible(m,n):

    if m!=n and m%n==0:
        return True

    elif n == 1:
        return False

    else:
        divisible(m, n-1)

primes()

(я использовал IDE в браузере, поэтому num часть была прокси для ввода.)

Моя идея заключалась в том, чтобы создать отдельную функцию divisible(), которая при вводе двух целых чисел, m и n, проверяла бы, делит ли n m. Я не уверен, был ли я прав в своей рекурсии, но я написал divisible(m,n-1), идея заключалась в том, что он будет перебирать все целые числа от n вниз и возвращать True, если есть n разделенный m или False, если достигнуто 1.

В основном коде m повторяется по всем числам в list, а n - это общее количество элементов в тот же list. Я помещаю print(numlist) в оператор if в качестве проверки на наличие ошибок. У меня проблема в том, что ничего не печатает. Код буквально ничего не вернул. Я что-то упустил из-за того, как здесь работает рекурсия?

Answer 1

Здесь много неправильного:

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

Кажется, что этот модуль обратный:

if ... and m%n==0:

Может быть, это должно быть:

if ... and n % m == 0:

You ' Код re, похоже, не вычисляет простые числа . Похоже, он вычисляет относительные простые числа до n.

Вы начинаете свой список чисел с 1:

numlist = list(range(1,num+1))

Но вы начинаете тестирование с индекса 2:

for j in numlist[2:]:

Это число 3, и вы никогда не проверяете делимость числа 2.

Даже со всеми этими исправлениями я не чувствую ваш алгоритм будет работать.

Answer 2

Ваша делимая функция ничего не возвращает, если она попадает в другую часть. измените его как

def divisible(m, n):
    if m!=m and m%n==0:
        return True
    elif n==1 :
        return False
    else:
        return divisible(m,n-1)

Это должно работать