Функция is_prime с использованием абстрактной функции фильтра - PullRequest
Новая
       37

Функция is_prime с использованием абстрактной функции фильтра

0 голосов
/ 27 октября 2019

Я пытаюсь использовать абстрактную функцию filter для решения проблемы is_prime. Я думаю, что это логично работает, но результат всегда будет ложным. и когда я добавляю «print (lon)», пытаюсь выяснить проблему. Он печатает что-то, чего я не понимаю.

Я попробовал рекурсивный способ, он работает. 

def is_prime(n):
    if n == 2:
        return True
    lon = filter (lambda x: n % x == 0, list(range (2, n)))
    if lon == []:
        return True
    else:
        return False

результат всегда будет ложным.

, добавив 

print(lon)

, работающий 

is_prime(7)

Результат - 

<filter object at 0x039456D0>
False

Ответы [ 3 ]

0 голосов
/ 27 октября 2019

Чтобы решить вашу непосредственную проблему, вы должны рассмотреть типы. Поскольку filter(…) возвращает объект-генератор типа filter, он никогда не может быть равен [] - объекту типа list. Таким образом, вы можете просто сделать if list(lon) == []: или, что еще лучше, if not any(lon): и вызвать его в день, функция будет работать так, как вы хотели.

Несколько советов:

  • сравнение с [] не очень Pythonic, пустой список считается False в любом случае
  • было бы лучше отказаться от if и else, а вместо return not any(lon)
  • однако, если вы просто хотите наиболее эффективно проверить, является ли данное число простым, вы можете пересмотреть свой подход - проверка n-2 чисел не является хорошей идеей;рассмотрим, например, что:
    • только один простой фактор может быть больше, чем sqrt(n), а не простые числа по определению имеют более одного этого фактора, поэтому вам нужно проверить только до sqrt(n)
    • четное число не является простым, поэтому вам нужно только проверять каждое другое число
  • и для чего-либо более профессионального используйте научно оптимизированный, чрезвычайно оптимизированный алгоритм, такой как Миллер–Тест на простоту Рабина (руководство по реализации см. В разделе «Детерминированные варианты»)
0 голосов
/ 27 октября 2019

Я бы предположил, что ваше текущее использование filter является неправильным подходом для генерации. Позволив filter сгенерировать complete результат, чтобы вы могли измерить его длину, вы потеряли все преимущества использования генератора!

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

def is_prime(n):
    if n <= 2 or n % 2 == 0:
        return n == 2

    return not any(filter(lambda x: n % x == 0, range(3, int(n ** 0.5) + 1, 2)))

Учитывая, что filter, any и range все ленивы, мы только завершаем генерациюв случае простого. Вам все равно, 15 имеет несколько простых делителей, но ваш оригинальный подход filter находит их обоих! Приведенный выше подход должен решить вопрос "является ли он простым" , как только он найдет свой первый делитель, а не смотреть дальше.

0 голосов
/ 27 октября 2019

Объект фильтра никогда не будет == в списке, поэтому вы всегда получите false. Вместо этого проверьте, является ли фильтр пустым. 

def is_prime(n):
    if n == 2:
        return True
    lon = filter (lambda x: n % x == 0, list(range (2, n)))
    try:
        min(lon)
    except ValueError:
        return True
    return False

Редактировать: еще чище 

def is_prime(n):
    if n == 2:
        return True
    lon = filter (lambda x: n % x == 0, list(range (2, n)))
    if not any(lon):
        return True
    else:
        return False
...