如何更有效地迭代python中的列表？

Question

我正在尝试创建一个程序，它返回任何给定数字的最大素数因子。代码适用于相对较小的数字，但一旦它们开始变大，代码就会花费很长时间。

memo = {}

def is_prime(n):
    if n not in memo:
        memo[n] = True
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                memo[n] = False
                return False
    return memo[n]


def prime_factors(n):
    factors = []
    prime_factor = []
    for i in range(n, 2, -1):
        if n % i == 0:
            factors.append(i)
    for num in factors:
            if is_prime(num):
                prime_factor.append(num)
                break
    print(prime_factor)

prime_factors()

反正是为了让它更有效率，我认为这与我指的是prime_factors函数中的另一个函数这一事实有关，这导致它效率非常低。

Answer 1

不幸的是，我不太了解你的方法，特别是为什么你总是从头开始计算is_prime(n)函数，这大大增加了大输入的复杂性。你的for num in factors:函数中的prime_factors(n)部分也对我没有多大意义。

但是，您可以尝试使用此解决方案：

import time


def get_next_prime(n: int = 0):
    if n < 1:
        return 2

    if 1 <= n < 3:
        return n + 1

    while True:
        n += 1

        # Corner cases
        if n % 2 == 0 or n % 3 == 0:
            continue

        i = 5
        not_prime = False
        # check till sqrt(n) because a larger factor of n must be
        # a multiple of smaller factor that has been already checked.
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                not_prime = True
                break

            i = i + 6

        if not_prime:
            continue

        return n


def prime_factors(dividend):
    # dividend : divisor = quotient (remainder)
    divisor = get_next_prime()
    quotient = -1

    factors = []

    while quotient != 0:
        remainder = dividend % divisor
        quotient = dividend // divisor

        if remainder == 0:
            factors.append(divisor)
            dividend = quotient
        else:
            divisor = get_next_prime(divisor)

    return factors

start = time.time()
print(prime_factors(899999999998))
end = time.time()
print(end - start)

看看这个演示：https://repl.it/repls/DefiantRecursiveWamp

---

关于适用的算法，请考虑以下示例：

术语：dividend : divisor = quotient (remainder)

即7：2 = 3（1）

问题：找出18的主要因素

1. 初始 获取divisor的下一个素数：即2
2. 18 : 2 = 9 (0) 余数0 拿2并更新dividend
3. 9 : 2 = 4 (1) 余数不是0 获取divisor的下一个素数：3​​; dividend保持不变
4. 9 : 3 = 3 (0) 余数0 拿3并更新dividend
5. 3 : 3 = 1 (0) 余数0 拿3并更新dividend
6. 1 : 3 = 0 (0) quotient是0 - >停止！

主要因素：{2, 3, 3}

Answer 2

你可以看看list comprehension，generator，itertools。和内置地图，过滤功能