Что не так с моим основным фильтрующим кодом? Это не вернет правильный список

Question

Я написал функцию filter_primes, которая должна (точно) отфильтровывать простые числа из заданного списка и выводить новый список только простых чисел. Когда я запускаю этот пример, я получаю >>> [9].
Мой мозг поражен. Может ли кто-нибудь указать мне правильное направление?

n = 2

def is_prime(num):
  global n
  if num%n != 0 and n<num:
    n = n + 1
    is_prime(num)
  elif n == num:
    return True
  else:
    return False

def filter_primes(list1):
  list2 = []
  for i in list1:
    if is_prime(i):
      list2.append(i)

  print(list2)


filter_primes([7, 9, 3, 9, 10, 11, 27])

Answer 1

Проблема в вашей функции is_prime. Поскольку вы делаете это рекурсивно, вы хотите разделить его на:

• Обработка базовых вариантов:
  1. Вы найдете n, который равномерно делит num, затем num не простое число
  2. Вы получите n больше num, тогда num простое число
• В противном случае вызовите вашу функцию рекурсивно с помощью n+1 и return это значение.

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

def is_prime(num, n=2):
  if n >= num:  # This could be made into sqrt(num) if you're trying to optimize this
      return True
  if num % n == 0:
      return False
  return is_prime(num, n+1)

Answer 2

Я решил это, открыв код в IDE (IntelliJ), а затем пошагово перебирая код, используя встроенный отладчик. Это поможет вам визуализировать происходящее. В противном случае попробуйте распечатать переменные внутри функции.

Первая проблема заключается в том, что вы используете global n. Это прекрасно работает для первого числа 7, но это число не сбрасывается для второго числа 9. Таким образом, происходит то, что is_prime(9) тестирует только против деления 8 (и поэтому возвращает true)

Это можно сделать в al oop вместо использования рекурсии, но так как вы при использовании рекурсии, n (как внутреннее состояние) можно обработать, передав это в качестве параметра функции со значением по умолчанию. Это будет сбрасывать n для каждого вызова верхнего уровня для n.

Также, так как вы рекурсивно вызываете is_prime(), вам нужно return is_prime(), чтобы гарантировать, что логическое значение, возвращаемое из вершины стека, будет возвращено, когда вы откручиваете назад на дно стека для оригинального абонента.

Ваш код случайно сработал для is_prime(9), потому что ваша логика c тестировалась только для 8, поэтому могла вернуться без отказов.

Вот рабочий код:

def is_prime(num, n=2):
    if num % n != 0 and n < num:
        n = n + 1
        return is_prime(num, n)
    elif n == num:
        return True
    else:
        return False

def filter_primes(list1):
    list2 = []
    for i in list1:
        if is_prime(i):
            list2.append(i)
    return list2


print( filter_primes([7, 9, 3, 9, 10, 11, 27]) )

$ primes.py
[7, 3, 11]

Также вам может быть интересно прочитать немного о prime number search algorithms.

Несколько простых оптимизаций :

• За исключением 2, все простые числа нечетны (поэтому вы можете сразу же вернуть False)
• Сито Эратосфена расширяет это далее
• Технически вам нужно только поиск до sqrt(num)
• Читайте о memoization (он же динамическое c программирование), так как вы можете кэшировать результаты предыдущих вызовов функций
• Добавить python подсказки типа и написать документацию за ваши функции (ваше будущее само будет благодарить вас, когда вы вернете код через месяц)

Рассмотрим новый вариант использования:

• сгенерируйте всю последовательность простых чисел ( вы начнете замечать проблемы с производительностью здесь)
• Добавьте таймер или используйте профилировщик внутри вашей IDE. Сравните, насколько быстро работает код, особенно для больших чисел. Эти предлагаемые оптимизации ускоряют процесс?