欧拉项目＃10

我对算法很陌生，刚开始编码周回来。请帮我出这一个：欧拉项目＃10

素数之和小于10为2 + 3 + 5 + 7 = 17

见以下两个万支全质数的总和。

我尝试通常的蛮力方法，该方法ofcourse吸入。我尝试阅读Sieve算法。并实现了这一点，是的，它只是为奇数运行：

i=[x for x in range(3,2000001,2)] 
print(len(i)) 
j=0 
sum=2 
while(max(i)!=j): 
    m=0 
    while(m<(2000000-(i[j]**2)/(2*i[j]))): 
     a=(i[j]**2)+2*m*i[j] 
     if a in i: 
      i.remove(a) 
     m+=1 
    j+=1 
for s in range(1,len(i)+1): 
    sum+=i[s] 
print(sum)

程序仍然需要像5个多小时。我在3小时内停止了它。我哪里错了？

来源

2014-04-25 Ashtrix

蛮力通常不够好项目欧拉问题。你必须找到一种加速找到正确答案的算法。看看“算法分析”或AofA领域。某些问题的一些算法非常高效，并且可以使您的加速达到百万倍。您还应该考虑记忆和动态编程（DP）。 –

看来你正在努力学习，所以我不会给你完整的解决方案，只是路径。

不要乱搞清单，把元素放入和放出，检查它们是否在，等等。这是低效率的秘诀。相反，保留已知素数列表。
写评论。我一直盯着你的代码几分钟，我不知道它的作用。
适用时使用math函数。 math.sqrt比**0.5快（约增加30％）。
此块： for s in range(1,len(i)+1): sum+=i[s] 伤害。您可以通过以下方式获得列表总和：打字sum(i)
[x for x in range(3,2000001,2)]与range(3,2000001,2)（在Python2中）或list(range(3,2000001,2))（在Python3中）完全相同。
不要使用变量名称为i，a，m。目前尚不清楚它们是什么。

你怎么知道一个数字是否是总数？对于它下面的所有素数，检查他们是否将你的数字分开。如果没有，请保存。事实上，您只能检查那些比数字的平方根小的素数。

如果你想交换内存的速度，你可以使用@vamosrafa的功能，并做sum(prime(2e6))。（在Python2中更改为range为xrange）。你只需要记忆同时保存几个数字，但是会做很多不必要的分割（如果它不能被3或5整除，它将不能被15整除）。

来源

2014-04-25 10:38:29 Davidmh

这些是一些非常方便的提示！万分感谢！ – Ashtrix

@Davidmh：是的，收益率方法会消耗内存，这就是为什么，这不是一个好方法，因为我一直在用筛选方法挣扎，它需要5个小时的时间。 – vamosrafa

我在同也卡住了，花了两个晚上出局，解决这个问题。

于是，我拿起Mark Pilgrim的DIVE INTO PYTHON，并有一个约发生器功能章节，我应用该技术来解决这个问题。下面是这将解决这个问题发生器功能：

def prime(max): 

    for n in range(2,max): 

     for x in range(2,int(n**0.5) + 1): 

      if n%x == 0: 


       break 
     else: 

      yield n

现在，写另一个函数总和，这将调用该方法，无论是在外壳或在这个程序本身，我曾呼吁在外壳的总和，但是这将解决你的问题。

祝你好运！ :)

来源

2014-04-25 10:16:52 vamosrafa

虽然通常用于测试素数的好方法，但这不能解决用户的问题（它们的实现有什么问题），也不会使用所提到的筛选方法。 – jonrsharpe

是的，我已经发布了一个优化方法，采用筛选方法，对我来说，处理时间相当于5小时。 – vamosrafa

哇，真的？！你在运行什么？在我的例子中相对天真的筛子花费了大约2秒。你可能想把你的代码放到http://codereview.stackexchange.com并获得一些帮助来加速它。 – jonrsharpe

筛是一种很好的方法，但是你的实现很混乱，显然不能正常工作。考虑这个非常简单的（未优化）的实现：

def prime_sieve(max_): 
    """Create a list containing all prime numbers equal to or less than max_.""" 
    primes = list(range(max_+1)) # all numbers 0 to max_ 
    primes[1] = 0 # 1 is not prime 
    for number in primes: # iterate through all numbers 
     if number: # if not 0 (i.e. prime) 
      for multiple in range(2, (max_ // number) + 1): 
       primes[number * multiple] = 0 # set multiples to zero 
    return primes

这可能更有效率，但是在大约两秒钟max_ == 2000000运行我的机器上。

使用for循环通常比用于迭代容器（如列表）的while循环更好。还要注意，我在列表中留下了非素数，但将它们设置为零 - 否则索引（代码中的i[j]）将会中断。

对于测试例如：

>>> prime_sieve(10) 
[0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0] 
>>> list(filter(None, prime_sieve(10))) 
[2, 3, 5, 7] 
>>> sum(prime_sieve(10)) 
17

来源

2014-04-25 10:43:14 jonrsharpe

一个改进能够基于@jonrsharpe提供的代码进行 - 取代for multiple in range(2, (max_//number)+1):与for multiple in range(number, (max_//number)+1):

def prime_sieve2(max_): 
     primes = list(range(max_+1)) 
     primes[1] = 0 
     for number in primes: 
       if number: 
         # starting from number rather than 2 
         for multiple in range(number, (max_//number)+1): 
           primes[number * multiple] = 0 
     return primes

前的评估步骤（你可以看到评估从2到数字^ 2可以跳过）：

check 2, 4, 6, 8, 10, 12, 14,... 
check 3, 6, 9, 12, 15, 18, 21,... (6 is already checked by '2') 
check 5, 10, 15, 20, 25, 30, 35,... (10, 15, 20 are already checked by '2' and '3') 
check 7, 14, 21, 28, 35, 42, 49, 56,... (again, 14, 21, 28, 35, 42 are redundant checked)

个

增强后的评估步骤：

check 4, 6, 8, 10, 12, 14,... 
check 9, 12, 15, 18, 21,... 
check 25, 30, 35, ... 
check 49, 56, ...

来源

2015-01-22 13:10:49

回答

相关问题