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

问题描述 投票:0回答:2

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


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函数中的另一个函数这一事实有关,这导致它效率非常低。

python-3.x
2个回答
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}


0
投票

你可以看看list comprehensiongeneratoritertools。和内置地图,过滤功能