欧拉项目在Python

＃3

我试图解决项目欧拉问题3在Python：欧拉项目在Python

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

来源

2012-11-21 user1843479

您在'primegen'中混合了'i'和'y'。至于错误，请尝试'xrange'。 –

像你在做的那样，在'mainfunction'里面引用变量'tab'是个坏习惯。你对'primegen（）'的调用可以返回素数列表，你可以给一个变量赋值：'primes = primegen（x）'，然后下一行'for xrange（len（primes））'。 – jozzas

欢迎来到Stackoverflow。我为你格式化了代码，但请看看[this]（http://stackoverflow.com/editing-help）和[this]（http://meta.stackexchange.com/a/22189），以及格式化代码块下次正确。 – BrtH

的原因是，在Python列表限制为536,870,912元（见How Big can a Python Array Get?），当你在你的例子创建范围，元素的数量超过了这个数字，导致错误。

欧拉计划的乐趣是自己弄清楚这些东西（我知道你在做:)），所以我会给出一个非常小的暗示来绕过这个错误。考虑一个数字的因素是什么 - 你知道600851475142是600851475143的因素是不可能的。因此，你不必检查一直到那个数字。遵循这个逻辑，是否有一种方法可以显着减少你检查的范围？如果您对素数因素的属性进行了一些研究，您可能会发现一些有趣的内容:)

来源

2012-11-21 22:56:04 RocketDonkey

您可以取代范围由xrange不将整个元素列表存储在内存中。 – barracel

非常感谢！ – user1843479

@barracel确实:)我将在短短一分钟内（在会议中:)添加更新） – RocketDonkey

首先，在第一个代码块中，不要使用i = i+1，因为for循环会处理它。其次，使用xrange来生成一个生成器而不是一个列表。

来源

2012-11-21 23:07:14

这是我使用的代码！

n = 600851475143 
i = 2 
while i * i < n: 
    while n % i == 0: 
     n = n/i 
    i = i + 1 

print n

-M1K3

来源

2013-03-02 02:59:46 seamonkey8

@ seamonkey8：您的代码可以得到改善。你可以增加2而不是1。它对真的很高的数字会产生速度差异：

n,i = 6008514751231312143,2 

while i*i <= n:  
    if n%i == 0: 
     n //= i 
    else: 
     i+=[1,2][i>2]

来源

2014-12-13 16:47:51

欧拉项目在Python

回答

相关问题