小练习：20160418 计算两百万以下所有质数的和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在4.26 10：00前完成，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。


题目：

10 以下的质数的和是 2 + 3 + 5 + 7 = 17.

找出两百万以下所有质数的和。

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

holdme

先占个座，效率不高

1. import time
   
2. import functools
   
3. start = time.clock()
   
4. from math import sqrt; from itertools import count, islice
   
5. 
   
6. def isPrime(n):
   
7.     return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
   
8. 
   
9. 
   
10. num_list = (2,) + tuple(range(3,2000000,2))
    
11. sum_p = functools.reduce(lambda x,y:x+y, (y for y in num_list if isPrime(y)))
    
12. print(sum_p)
    
13. print('%s'%(time.clock()-start))

复制代码

结果是：

1. 2148933

复制代码

旺仔sama

1. list1 = [2]
   
2. summation = 2
   
3. for i in range(3,2000000,2):
   
4.     for j in list1:
   
5.         quotient = i // j
   
6.         remainder = i % j
   
7.         if remainder == 0:
   
8.             break
   
9.         elif quotient < j:
   
10.             summation += i
    
11.             list1.append(i)
    
12.             break
    
13. 
    
14. print(summation)

复制代码

= = 不会优化了  200W好大。

dvdvdv

print (sum([i for i in range(1, 2000001) if not [j for j in range(2, i // 2 +1) if i % j == 0]]))
结果：142913828922

挥舞乾坤

python风格版:

1. prime = lambda max=2000000:sum((x for x in range(3,max,2) if all(x % y for y in range(3,int(x**.5)+1))))+2
   
2. print(prime())

复制代码

纯循环版:

1. def prime(max=2000000):
   
2.     sum = 2
   
3.     for n in range(3,max+1,2):
   
4.         for i in range(3, int(n**.5)+1):
   
5.             if n % i == 0:
   
6.                 break
   
7.         else:
   
8.             sum += n
   
9.     return sum
   
10. print(prime())

复制代码

最好理解的版本:

1. def prime(max=2000000):
   
2. 
   
3.     def isprime(num): #判断是不是质数
   
4.         for i in range(3,int(num**.5)+1):
   
5.             if num % i == 0:
   
6.                 return False
   
7.         return True
   
8. 
   
9.     sum = 2
   
10.     for n in range(3,max+1,2):#质数肯定是奇数(当然除了2意外)
    
11.         if isprime(n):
    
12.             sum += n
    
13. 
    
14.     return sum
    
15.    
    
16. print(prime())
    

复制代码

再来一个类的版本:

1. class Prime:
   
2.     def __init__(self,max=2000000):
   
3.         self.max = max
   
4.         self.first = True
   
5.         self.nums = iter(range(3, max+1, 2))
   
6. 
   
7.     def __next__(self):
   
8.         if self.first:
   
9.             self.first = False
   
10.             return 2
    
11.         
    
12.         while True:
    
13.             i = next(self.nums)
    
14.             if all(i % j for j in range(3, int(i**.5)+1)):
    
15.                 return i
    
16.             
    
17.     def __iter__(self):
    
18.         return self
    
19.    
    
20.     def sum(self):
    
21.         return sum(self)
    
22. 
    
23. print(Prime().sum())
    

复制代码

DingRan

严重支持

1. import math
   
2. 
   
3. def primeTest(num):
   
4.     for i in range(2, int(math.sqrt(num))+1):
   
5.         if num%i==0:
   
6.             return False
   
7.     return True
   
8. 
   
9. def primeSum(n):
   
10.     result = 2
    
11.     if n < 3:
    
12.         return result - 2
    
13.     if n == 3:
    
14.         return result
    
15.     i = 3
    
16.     while i < n:
    
17.         if primeTest(i):
    
18.             result += i
    
19.         i += 2
    
20.     return result
    
21. 
    
22. print(primeSum(2000000))

复制代码

运行结果

1. >>>
   
2. 142913828922
   
3. >>>

复制代码

小火木

1. def primesum(n):
   
2.     import math
   
3.     lis1=[2]
   
4.     nem=3
   
5.     while nem<=n:
   
6.         val=1
   
7.         for i in lis1:
   
8.             if i >math.sqrt (nem):
   
9.                 break
   
10.             elif nem%i==0:
    
11.                 val=0
    
12.                 break
    
13.         if val:
    
14.             lis1.append(nem)
    
15. 
    
16.         nem+=2
    
17.     print(sum(lis1))
    
18. 
    
19. 
    
20. import time
    
21. t1=time.clock()
    
22. primesum(2000000)
    
23. t2=time.clock ()
    
24. print(t2-t1)
    

复制代码

caobynk

1. def sumPrime(upLimte):
   
2.     num = list(range(2, upLimte+1))
   
3.     # 去掉偶数
   
4.     for k in range(2, int(upLimte/2)+1):
   
5.         num[2*k-2] = 0
   
6. 
   
7.     for i in range(1, len(num)):
   
8.         if num[i] != 0:
   
9.             for k in range(3, int(upLimte/num[i])+1, 2):
   
10.                 num[num[i]*k-2] = 0
    
11.     return sum(num)
    
12. 
    
13. if __name__ == '__main__':
    
14.     print(sumPrime(2000000))

复制代码

lingtingliushen

1. import math
   
2. def isPrime(n):
   
3.     if n <= 1:
   
4.         return False
   
5.     for i in range(2,int(math.sqrt(n)) + 1):
   
6.         if n % i == 0:
   
7.             return False
   
8.     return True
   
9. n=2
   
10. s=0
    
11. while n <= 2000000:
    
12.     if isPrime(n):
    
13.         s += n
    
14.     n += 1
    
15. print('2000000以下的质数的和是%d' % s)

复制代码

1. 2000000以下的质数的和是142913828922

复制代码

老忘

1. # -*- coding: utf-8 -*-
   
2. import math
   
3. 
   
4. def isPrime(n):#质数判断
   
5.         if n == 1:
   
6.                 return False
   
7.         elif n < 4:
   
8.                 return True
   
9.         elif n & 1 == 0:
   
10.                 return False
    
11.         elif n < 9:
    
12.                 return True
    
13.         elif n %3 == 0:
    
14.                 return False
    
15.         else:
    
16.                 r = math.floor(math.sqrt(n))
    
17.                 f = 5
    
18.                 while f <= r:
    
19.                         if n % f == 0:
    
20.                                 return False
    
21.                         if n %(f+2) == 0:
    
22.                                 return False
    
23.                         f += 6
    
24.                 return True
    
25. 
    
26. a=2
    
27. i=3
    
28. while (i<2000001):
    
29.     if isPrime(i):a=a+i
    
30.     i=i+2
    
31. print(a)

复制代码

感觉效率不高，但不知应再如何减少循环了，看来思路是很重要的啊！

小剑剑

1. def a(n):
   
2.     a=[1]*(n+1)
   
3.     m=2
   
4.     su=0
   
5.     while m<=n:
   
6.         if a[m]:
   
7.             su+=m
   
8.             l=2*m
   
9.             while l<=n:
   
10.                 a[l]=0
    
11.                 l+=m
    
12.         m+=1
    
13.     return su
    
14. print(a(2000000))
    

复制代码

结果142913828922

呆鸭

1. primes=[2]
   
2. for num in range(3,2000000):
   
3.         isPrime=True
   
4.         for prime in primes:
   
5.                 sqr=prime**2
   
6.                 if num<sqr:
   
7.                         break
   
8.                 else:
   
9.                         if num%prime==0:
   
10.                                 isPrime=False
    
11.                                 break
    
12.         if isPrime:
    
13.                 primes.append(num)
    
14. print(sum(primes))

复制代码

2012277033

按照提意，最小的质数是2所以number＝2
然后用两个循环来让除数和被除数递进。
用a来判断number的因数，当因数大于2时就跳出一层循环，来减少运算时间
用b来接收质数的值并加起来。

1. number = 2
   
2. num = 1
   
3. a = 0
   
4. b=0
   
5. while number <= 2000000:
   
6.     while num <= number:
   
7.         if number%num == 0:
   
8.             a+=1
   
9.         num+=1
   
10.         if a>2:
    
11.             break
    
12.     if a == 2:
    
13.         b=b+number
    
14.     num=1
    
15.     number+=1
    
16.     a=0
    
17.    
    
18. print(b)

复制代码

zzh-nju

1. from math import *
   
2. 
   
3. def is_prime(n):
   
4.     if n == 2 or n == 3:
   
5.         return True
   
6.     for num in range(2, int(sqrt(n) + 1)):
   
7.         if n % num == 0:
   
8.             return False
   
9.             break
   
10.     return True
    
11. 
    
12. def get_prime(num):
    
13.     while True:
    
14.         if is_prime(num):
    
15.             yield num
    
16.         num += 1
    
17. 
    
18. PRIME = get_prime(2)
    
19. sum = 0
    
20. for each in PRIME:
    
21.     if each < 2000000:
    
22.         sum += each
    
23.     else:
    
24.         break
    
25. 
    
26. print(sum)
    
27.    

复制代码

运行结果：

1. 142913828922

复制代码

宝贝归来

1. h = 0
   
2. for i in range(2,11): # 200万算了好久，算不出来，2万还行，20万都费劲（T_T）
   
3.     c = 0
   
4.     for a in range(2,i+1):        
   
5.         if( i%a == 0 ):
   
6.             c = c + 1
   
7.     if(c==1):
   
8.         h = h + i
   
9. print(h)

复制代码

mypython

sum=2   #定义相加的和先为2
b=0       #给判断有没有被1和本身以外的数整除的数一个初值
a=int(input('输入范围:'))      #输入范围
for i in range(3,a+1):          #循环从3开始到范围
    for j in range(2,i):           #循环判断从2到轮到的范围数
        if (i%j==0):                #判断有没有被1和本身以外的数整除
            b=0                       #如果被1和本身以外的数整除,记录0
            break                    #推出循环
        else:                          #再判断
            b=1                      #如果没有被1和本身以外的数整除,记录1
    if b==1:                       #循环结束后判断书不是质数
        sum+=i                   #判断是质数,相加
print(sum)                       #输出相加

代码缺点数目太大运行会很久

mather

1. def is_prime(x):
   
2.     flag = True
   
3.     sqrt_x = x**(0.5)
   
4.     i = 2
   
5.     while i<=sqrt_x:
   
6.         if x%i==0:
   
7.             flag = False
   
8.             break
   
9.         i += 1
   
10.     return flag
    
11. 
    
12. a = (2*i+1 for i in range(1,1000000) if is_prime(2*i+1))
    
13. print(sum(a)+2)
    

复制代码

定义个判定质数的方法，然后放到生成器中判定。最后加和引发生成器计算。效率一般，没统计多少秒算出来，大概10s以内吧。
前几天写过一个埃氏筛法，算法思路挺好的，就是运算效率太低了。

Hewee

1. from math import sqrt
   
2. 
   
3. num=2+3+5+7+11
   
4. 
   
5. def isprime(n):
   
6.     for i in range(2,int(sqrt(n))+1):
   
7.         if n % i == 0:
   
8.             return False
   
9.     return True
   
10. 
    
11. for i in range(11,2000000,2):
    
12.     if i%3!=0 and i%5!=0 and i%7!=0 and i%11!=0 and isprime(i):
    
13.         num=num+i
    
14. 
    
15. print(num)

复制代码

能力有限，只能做到这个程度了

zzh-nju

1. from math import *
   
2. import time
   
3. 
   
4. def is_prime(n):
   
5.     if n == 2 or n == 3:
   
6.         return True
   
7.     if n % 2 == 0:
   
8.         return False
   
9.     else:
   
10.         for num in range(3, int(sqrt(n) + 1), 2):
    
11.             if n % num == 0:
    
12.                 return False
    
13.                 break
    
14.         return True
    
15. 
    
16. def get_prime(num):
    
17.     while True:
    
18.         if is_prime(num):
    
19.             yield num
    
20.         num += 1
    
21. 
    
22. t1= time.time()
    
23. PRIME = get_prime(2)
    
24. sum = 0
    
25. for each in PRIME:
    
26.     if each < 2000000:
    
27.         sum += each
    
28.     else:
    
29.         break
    
30. 
    
31. print(sum)
    
32. print(time.time()-t1)  
    

复制代码

运行结果

1. 142913828922
   
2. 24.587407112121582

复制代码

loyfee

1. def isPrime(x):
   
2.     import math
   
3.     return_re = 1   
   
4.     if x in (2,3):
   
5.         return 1
   
6.     elif x >= 4:
   
7.         for i in range(2,int(math.sqrt(x))+1):
   
8.             if x % i == 0:
   
9.                 return_re = 0
   
10.         return return_re
    
11. 
    
12. def add_Prime(x):
    
13.     sum = 2
    
14.     for i in range(3,x+1,2):
    
15.         if isPrime(i) == 1:
    
16.             sum += i
    
17.     print(sum)

复制代码

执行:add_Prime(2000000)
第一个模块用于判断是否为素数，第二个函数用于叠加素数，一直到x
计算结果：142913828922
时间用的好长，好像一分钟以上