加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Python > 正文

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的因子.因此你不必一直检查这个数字.遵循这个逻辑,有没有办法可以大大减少你检查的范围?如果你对素因子的属性做了一些研究,你可能会发现一些有趣的东西:)

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读