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

冬雪雪冬 · 发表于 2016-4-18 10:00:00

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-4-26 11:20 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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 · 发表于 2016-4-18 13:16:35

本帖最后由 holdme 于 2016-4-18 16:37 编辑

先占个座，效率不高

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 · 发表于 2016-4-18 14:21:32

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 · 发表于 2016-4-18 16:48:52

本帖最后由 dvdvdv 于 2016-4-18 21:41 编辑

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

挥舞乾坤 · 发表于 2016-4-18 17:31:26

本帖最后由挥舞乾坤于 2016-4-18 19:08 编辑

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 · 发表于 2016-4-18 19:25:14

严重支持

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
>>>

复制代码

小火木 · 发表于 2016-4-18 22:02:04

本帖最后由小火木于 2016-4-18 22:07 编辑

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 · 发表于 2016-4-18 22:59:23

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 · 发表于 2016-4-19 08:58:55

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

复制代码

老忘 · 发表于 2016-4-19 09:12:27

# -*- 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)

复制代码

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

小剑剑 · 发表于 2016-4-19 11:04:14

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

呆鸭 · 发表于 2016-4-19 19:44:52

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 · 发表于 2016-4-20 16:16:50

本帖最后由 2012277033 于 2016-4-21 11:13 编辑

按照提意，最小的质数是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 · 发表于 2016-4-21 19:21:09

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

复制代码

宝贝归来 · 发表于 2016-4-21 20:04:56

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 · 发表于 2016-4-22 09:54:11

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 · 发表于 2016-4-22 10:33:57

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 · 发表于 2016-4-22 15:22:57

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 · 发表于 2016-4-23 18:05:01

本帖最后由 zzh-nju 于 2016-4-23 18:07 编辑

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 · 发表于 2016-4-23 22:21:16

本帖最后由 loyfee 于 2016-4-23 22:23 编辑

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
时间用的好长，好像一分钟以上

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20160418 计算两百万以下所有质数的和

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

点评

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分