小练习：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

先占个座，效率不高

import time
import functools
start = time.clock()
from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))


num_list = (2,) + tuple(range(3,2000000,2))
sum_p = functools.reduce(lambda x,y:x+y, (y for y in num_list if isPrime(y)))
print(sum_p)
print('%s'%(time.clock()-start))

结果是：

2148933

旺仔sama

list1 = [2]
summation = 2
for i in range(3,2000000,2):
    for j in list1:
        quotient = i // j
        remainder = i % j
        if remainder == 0:
            break
        elif quotient < j:
            summation += i
            list1.append(i)
            break

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风格版:

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
print(prime())

纯循环版:

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

最好理解的版本:

def prime(max=2000000):

    def isprime(num): #判断是不是质数
        for i in range(3,int(num**.5)+1):
            if num % i == 0:
                return False
        return True

    sum = 2
    for n in range(3,max+1,2):#质数肯定是奇数(当然除了2意外)
        if isprime(n):
            sum += n

    return sum
    
print(prime())

再来一个类的版本:

class Prime:
    def __init__(self,max=2000000):
        self.max = max
        self.first = True
        self.nums = iter(range(3, max+1, 2))

    def __next__(self):
        if self.first:
            self.first = False
            return 2
        
        while True:
            i = next(self.nums)
            if all(i % j for j in range(3, int(i**.5)+1)):
                return i
            
    def __iter__(self):
        return self
    
    def sum(self):
        return sum(self)

print(Prime().sum())

DingRan

严重支持

import math

def primeTest(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True

def primeSum(n):
    result = 2
    if n < 3:
        return result - 2
    if n == 3:
        return result
    i = 3
    while i < n:
        if primeTest(i):
            result += i
        i += 2
    return result

print(primeSum(2000000))

运行结果

>>> 
142913828922
>>> 

小火木

def primesum(n):
    import math
    lis1=[2]
    nem=3
    while nem<=n:
        val=1
        for i in lis1:
            if i >math.sqrt (nem):
                break
            elif nem%i==0:
                val=0
                break
        if val:
            lis1.append(nem)

        nem+=2
    print(sum(lis1))


import time
t1=time.clock()
primesum(2000000)
t2=time.clock ()
print(t2-t1)

caobynk

def sumPrime(upLimte):
    num = list(range(2, upLimte+1))
    # 去掉偶数
    for k in range(2, int(upLimte/2)+1):
        num[2*k-2] = 0

    for i in range(1, len(num)):
        if num[i] != 0:
            for k in range(3, int(upLimte/num[i])+1, 2):
                num[num[i]*k-2] = 0
    return sum(num)

if __name__ == '__main__':
    print(sumPrime(2000000))

lingtingliushen

import math
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2,int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
n=2
s=0
while n <= 2000000:
    if isPrime(n):
        s += n
    n += 1
print('2000000以下的质数的和是%d' % s)

2000000以下的质数的和是142913828922

老忘

# -*- coding: utf-8 -*-
import math

def isPrime(n):#质数判断
        if n == 1:
                return False
        elif n < 4:
                return True
        elif n & 1 == 0:
                return False
        elif n < 9:
                return True
        elif n %3 == 0:
                return False
        else:
                r = math.floor(math.sqrt(n))
                f = 5
                while f <= r:
                        if n % f == 0:
                                return False
                        if n %(f+2) == 0:
                                return False
                        f += 6
                return True

a=2
i=3
while (i<2000001):
    if isPrime(i):a=a+i
    i=i+2
print(a)

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

小剑剑

def a(n):
    a=[1]*(n+1)
    m=2
    su=0
    while m<=n:
        if a[m]:
            su+=m
            l=2*m
            while l<=n:
                a[l]=0
                l+=m
        m+=1
    return su
print(a(2000000))

结果142913828922

呆鸭

primes=[2]
for num in range(3,2000000):
        isPrime=True
        for prime in primes:
                sqr=prime**2
                if num<sqr:
                        break
                else:
                        if num%prime==0:
                                isPrime=False
                                break
        if isPrime:
                primes.append(num)
print(sum(primes))

2012277033

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

number = 2
num = 1
a = 0
b=0
while number <= 2000000:
    while num <= number:
        if number%num == 0:
            a+=1
        num+=1
        if a>2:
            break
    if a == 2:
        b=b+number
    num=1
    number+=1
    a=0
    
print(b)

zzh-nju

from math import *

def is_prime(n):
    if n == 2 or n == 3:
        return True
    for num in range(2, int(sqrt(n) + 1)):
        if n % num == 0:
            return False
            break
    return True

def get_prime(num):
    while True:
        if is_prime(num):
            yield num
        num += 1

PRIME = get_prime(2)
sum = 0
for each in PRIME:
    if each < 2000000:
        sum += each
    else:
        break

print(sum)
    

运行结果：

142913828922

宝贝归来

h = 0
for i in range(2,11): # 200万算了好久，算不出来，2万还行，20万都费劲（T_T）
    c = 0
    for a in range(2,i+1):        
        if( i%a == 0 ):
            c = c + 1
    if(c==1):
        h = h + i
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

def is_prime(x):
    flag = True
    sqrt_x = x**(0.5)
    i = 2
    while i<=sqrt_x:
        if x%i==0:
            flag = False
            break
        i += 1
    return flag

a = (2*i+1 for i in range(1,1000000) if is_prime(2*i+1))
print(sum(a)+2)

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

Hewee

from math import sqrt

num=2+3+5+7+11

def isprime(n): 
    for i in range(2,int(sqrt(n))+1): 
        if n % i == 0: 
            return False
    return True
 
for i in range(11,2000000,2):
    if i%3!=0 and i%5!=0 and i%7!=0 and i%11!=0 and isprime(i):
        num=num+i

print(num)

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

zzh-nju

from math import *
import time

def is_prime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    else:
        for num in range(3, int(sqrt(n) + 1), 2):
            if n % num == 0:
                return False
                break
        return True

def get_prime(num):
    while True:
        if is_prime(num):
            yield num
        num += 1

t1= time.time()
PRIME = get_prime(2)
sum = 0
for each in PRIME:
    if each < 2000000:
        sum += each
    else:
        break

print(sum)
print(time.time()-t1)  

运行结果

142913828922
24.587407112121582

loyfee

def isPrime(x):
    import math
    return_re = 1    
    if x in (2,3):
        return 1
    elif x >= 4:
        for i in range(2,int(math.sqrt(x))+1):
            if x % i == 0:
                return_re = 0
        return return_re

def add_Prime(x):
    sum = 2
    for i in range(3,x+1,2):
        if isPrime(i) == 1:
            sum += i
    print(sum)

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