Python中列表的作用域 - Project Euler 007
这是我在这里的第一个问题。我正在通过解决Project Euler的问题来学习Python，但遇到了一些困难。下面这个方法（返回一个质因数的列表）在单次调用时工作得很好：
def findPrimeFactors(num, primeFactors = []):
'''Find the prime factors of an arbitrary positive integer
input: num to factorize
returns: a list containing the prime factors of the number
'''
pIndex = 2
while (num >= pIndex):
if num % pIndex == 0:
num /= pIndex
primeFactors.append(pIndex)
return FindPrimes.findPrimeFactors(num, primeFactors)
else:
pIndex += 1
return primeFactors
但是当我在一个循环中使用它时，就出现了问题（这个方法可能还不完整，目前在循环中会导致无限循环，因为找不到更多的质数）：
def countPrimes(n = 1001):
'''find n amount of unique primes ascending
input: number of primes to find
returns: list of n primes starting from 2 '''
primes = []
i = 2
while len(primes) < n:
primeFactors = FindPrimes.findPrimeFactors(i)
print(primeFactors) #verify method behavior
if len(primeFactors) is 1:
primes.append(primeFactors[0])
i += 1
return primes
结果是，第一次循环返回的是[2]，第二次返回的是[2, 3]，依此类推，把新的结果添加到我希望在第一次递归调用时是空的列表中。看起来我的列表是持续存在的，但我不太明白为什么？我也读了一些关于Python类作用域和列表的内容，这给了我一些线索，但递归让事情变得更复杂。
递归的意思是我也不能简单地给它赋一个空的集合。因为我之前是用C++的，所以我原本以为每次从我的程序调用这个函数时，primeFactors变量应该会重新初始化。但我在Python这方面还是个新手。
编辑：这是我写的findPrimeFactors的迭代版本。我知道它不是最优的，但我希望至少能让它高效到符合Project Euler的1分钟规则。任何改进或澄清的建议都非常感谢。
PRIMES = [2,3,5,7,11,13,17,19]
import math
class FindPrimes():
'''V2 iterative'''
def findPrimeFactors(n, primeFactors = None):
'''Find the prime factors of an arbitrary positive integer
input: num to factorize
returns: a list containing the prime factors of the number
'''
if primeFactors is None:
primeFactors = []
num = n
ceil = math.sqrt(n) #currently unused
global PRIMES
knownPrimes = PRIMES
#check known primes for divisors first, then continue searching for primes by brute force
while True:
factorFound = False
for prime in knownPrimes:
if num % prime == 0:
primeFactors.append(prime)
num /= prime
factorFound = True
break #ensure that the list returned has ascending primes
if not factorFound:
break
#once attempts have been made to reduce using known primes
#search for new primes if the number is not fully reduced
i = knownPrimes[-1] + 2
while num != 1:
if num % i == 0:
knownPrimes.append(i)
primeFactors.append(i)
num /= i
i += 2
return primeFactors
def countPrimes(n = 10001):
'''find n amount of unique primes ascending
input: number of primes to find
returns: list of n primes starting from 2 '''
primes = []
i = 2
while len(primes) < n:
primeFactors = FindPrimes.findPrimeFactors(i)
if len(primeFactors) == 1:
primes.append(primeFactors[0])
#print(primeFactors[-1])
i += 1
print(len(primes))
return primes
nth = 10001
print(FindPrimes.countPrimes(nth)[nth-1]) #print the largest prime found
3 个回答
1
正如hammar提到的，默认值只会在函数定义的时候创建一次，并且在多次调用时会共享这个值。
解决这个问题的常见方法是使用一个标记值作为默认值：
def findPrimeFactors(num, primeFactors=None):
if primeFactors is None:
primeFactors = []
...
题外话，你的函数 findPrimeFactor() 每找到一个质因数就会递归一次。Python并不会自动优化尾递归，所以你可能应该考虑用循环来重写这个函数，而不是用递归。
1
默认情况下，primeFactors的值在多次调用之间是共享的，也就是说，当你修改了这个值后，以后的调用也会受到影响，保持这个修改。
举个例子：
def foo(bar = []):
bar.append(1)
return bar
print foo()
print foo()
输出结果：
[1]
[1, 1]
你应该返回一个新的列表，而不是直接修改默认值：
def foo(bar = []):
return bar + [1]
print foo()
print foo()
输出结果：
[1]
[1]
3