Python中的Euler Project#3
发布时间:2020-12-20 12:29:19 所属栏目:Python 来源:网络整理
导读:我正在尝试用 Python解决Project Euler问题3: The prime factors of 13195 are 5,7,13 and 29.What is the largest prime factor of the number 600851475143 ? 我知道我的程序效率低且超大,但我只是想知道它为什么不起作用? 这是代码: def check(z):# ch
我正在尝试用
Python解决Project Euler问题3:
The prime factors of 13195 are 5,7,13 and 29. What is the largest prime factor of the number 600851475143 ? 我知道我的程序效率低且超大,但我只是想知道它为什么不起作用? def check(z): # checks if the given integer is prime for i in range(2,z): if z % i == 0: return False break i = i+1 return True def primegen(y): # generates a list of prime integers in the given range tab = [] while y >= 2: if check(y) == True: tab.append(y) i = i-1 def mainfuntion(x): # main function; prints the largest prime factor of the given integer primegen(x) for i in range(len(tab)): if x % tab[i] == 0: print tab[i] break mainfuntion(600851475143) 这是错误: for i in range(2,z): OverflowError: range() result has too many items 解决方法
原因是Python中的列表限制为536,870,912个元素(参见
How Big can a Python Array Get?),当您在示例中创建范围时,元素数量超过该数量,从而导致错误.
Project Euler的乐趣在于自己搞清楚这些东西(我知道你正在做的:)),所以我会给出一个非常小的提示来绕过这个错误.想想一个数字的因素是什么 – 你知道600851475142不可能是600851475143的因子.因此你不必一直检查这个数字.遵循这个逻辑,有没有办法可以大大减少你检查的范围?如果你对素因子的属性做了一些研究,你可能会发现一些有趣的东西:) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |