is_prime 函数使用过滤器抽象函数

Question

我正在尝试使用 '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

Answer 1

过滤器对象永远不会 == 到列表中，所以你总是得到 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

Answer 2

要解决您眼前的问题，您需要考虑类型。因为 filter(…) returns 类型 filter 的生成器对象，它永远不会等于 [] – list 类型的对象。所以你可以只做 if list(lon) == []: 或者，更好的是 if not any(lon): 然后收工，该函数将按照你想要的方式工作。

一些提示：

与 [] 相比不是很 Pythonic，空列表被认为是 False 无论如何
最好放弃 if 和 else，取而代之的是 return not any(lon)
然而，如果您只想最有效地检查给定数字是否为质数，您可能需要重新考虑您的方法——检查 n-2 个数字不是一个好主意；例如考虑：
- 只有一个素数因子可以大于 sqrt(n)，非素数根据定义有不止一个因子，所以您只需要检查最多 sqrt(n)
- 没有偶数是质数，所以你只需要检查每隔一个数
对于更专业的东西，请使用经过科学证明的极其优化的算法，例如 the Miller–Rabin primality test（请参阅 "Deterministic variants" 部分以了解实施指南）

Answer 3

我建议您目前对 filter 的使用在生成器方面是错误的方法。通过让 filter 生成完整结果以便您可以测量它的长度，您已经失去了使用生成器的任何优势！

而是考虑一种生成器方法，如果在生成中的任何一步我们检测到无余数除法，整个生成链就会停止，我们 return 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 方法找到了它们！上述方法应该在找到第一个除数后立即解决 "is it a prime" 问题，而不是进一步寻找。

is_prime 函数使用过滤器抽象函数

is_prime function using filter abstract function

python

primes

generator