# 如何更有效地迭代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()

``````

python-3.x
##### 2个回答
1

``````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)
``````

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 - >停止！

0