题目10：计算两百万以下所有质数的和

梦想绘制者 · 发表于 2016-11-12 15:42:57

def isPrime(n):
if n <= 1:
return False
else:
half = int(n ** 0.5)
for i in range(2,half + 1):
if n % i == 0:
return False
return True
def SumOfPrimesBelow(n):
SumPrm = 0
for i in range(2, n):
if isPrime(i):
SumPrm += i
return SumPrm
n = int(2E6)
Sum = SumOfPrimesBelow(n)
print('小于%d的质数的和为%d'%(n, Sum))

复制代码

>>>
小于2000000的质数的和为142913828922

梦想绘制者 · 发表于 2016-11-12 16:06:32

jerryxjr1220 发表于 2016-10-10 19:23
最快的求质数的方法：
142913828922
[Finished in 1.8s]

果然好快啊！能解释一下的话就更完美了。

梦想绘制者 · 发表于 2016-11-12 16:08:05

jerryxjr1220 发表于 2016-10-10 19:23
最快的求质数的方法：
142913828922
[Finished in 1.8s]

果然好快啊！能解释一下的话就更完美了。

jerryxjr1220 · 发表于 2016-11-12 16:58:31

梦想绘制者发表于 2016-11-12 16:08
果然好快啊！能解释一下的话就更完美了。

用的是标记法，先建一个列表，列表的项数等于要求的最大质数，内容都为True。
然后第0,1项设为False，因为0和1都不是质数。
从第2项开始，是2的倍数的项都是设为假，因为都不是质数。然后只要是列表内还没有设为假的数，从它开始，它的倍数都设为假，直到列表内全部为真的数，那就是质数。
原理就是这样。
利用列表的项数和列表值的对应关系。这样可以减少判断次数，当然速度就是最快的了。

梦想绘制者 · 发表于 2016-11-16 08:54:10

谢谢，这是以空间换时间的好方法啊，可以进一步优化的，先判断奇偶性，偶数不存储只判断奇数。哈哈，网上看了一下。

lyciam · 发表于 2016-11-18 10:39:51

import math
import time
t=time.clock()
def isprime(n):
if (n%2 == 0 and n!=2) or n == 1: return False
for x in range(3,int(math.sqrt(n))+1,2):
if n%x==0: return False
else: return True
def euler10(count=2000000):
result = []
for n in range(count):
if isprime(n): result.append(n)
return sum(result)
print (euler10(),'--time: ',time.clock()-t)

复制代码

142913828922 --time: 9.045785321932144

jerryxjr1220 · 发表于 2016-11-19 07:47:02

梦想绘制者发表于 2016-11-16 08:54
谢谢，这是以空间换时间的好方法啊，可以进一步优化的，先判断奇偶性，偶数不存储只判断奇数。哈哈，网上看 ...

一开始也想过，但是我建立列表的时候没有办法只建立奇数列表而没有偶数，如果要每次判断奇偶的话，其实计算时间就不见得比我短了。

梦想绘制者 · 发表于 2016-11-20 11:04:50

jerryxjr1220 发表于 2016-11-19 07:47
一开始也想过，但是我建立列表的时候没有办法只建立奇数列表而没有偶数，如果要每次判断奇偶的话，其实计 ...

嗯，有可能。这要看追求的是什么了。如果是仅仅速度快的话，你的完全可以。但又要快又要耗得空间少的话，分奇偶还是很可观的，毕竟一下都可以去掉一半的存储空间了。

芒果加黄桃 · 发表于 2017-1-9 11:28:25

purplenight 发表于 2016-8-7 08:03
# 修改自我的另一份代码, 部分代码或差劲, 能出结果就行.

这是过筛子的方法啊，好快

芒果加黄桃 · 发表于 2017-1-9 11:31:09

# encoding:utf-8
from math import sqrt
from time import time
def euler010(N=2000000):
l_pn = [2, 3]
result = 0
for n in range(5, N, 2):
# 标志位
ispm = True
sqr_n = int(sqrt(n))
for t in l_pn:
if n % t == 0:
ispm = False
break
if t > sqr_n:
break
if ispm:
l_pn.append(n)
print('小于 %d 的所有质数之和是： %d' % (N, sum(l_pn)))
return result
start = time()
euler010()
print('cost %.3f sec' % (time() - start))

复制代码

小于 2000000 的所有质数之和是： 142913828922
cost 4.122 sec

渡风 · 发表于 2017-1-13 16:39:58

此代码使用matlab编程
Problem10所用时间为54.8729秒
Problem10的答案为142913828922

%题目10：计算两百万以下所有质数的和
function Output=Problem10(Input)
tic
if nargin==0
Input=2000000;
end
Sum=2;
Temp=3:Input;
Temp1=4:2:Input;%筛选2的倍数
Temp2=6:3:Input;%筛选3的倍数
Temp3=10:5:Input;%筛选5的倍数
Temp4=14:7:Input;%筛选7的倍数
Temp5=22:11:Input;%筛选11的倍数
New1=setdiff(Temp,Temp1);
New2=setdiff(New1,Temp2);
New3=setdiff(New2,Temp3);
New4=setdiff(New3,Temp4);
New5=setdiff(New4,Temp5);
for ii=New5
if isprime(ii)==1
Sum=ii+Sum;
end
end
Output=Sum;
toc
disp('此代码使用matlab编程')
disp(['Problem10所用时间为',num2str(toc),'秒'])
disp(['Problem10的答案为',num2str(Output)])
end

复制代码

FlySelf · 发表于 2017-2-2 21:35:43

import time
def sum_of_primes(number):
'筛法找出所有质数，并求和'
result = 0
list_primes = [True] * (number + 1)
list_primes[0] = False
list_primes[1] = False
for i in range(2, number):
if list_primes[i]:
for j in range(i ** 2, number, i):
list_primes[j] = False
list_result = []
for k in range(2, number):
if list_primes[k]:
list_result.append(k)
for each in list_result:
result += each
return result
start = time.clock()
print(sum_of_primes(2000000))
end = time.clock()
print('程序执行了%fs。' %(end - start))

复制代码

执行结果：
142913828922
程序执行了1.113385s。

piperacillin · 发表于 2017-2-17 16:41:08

本帖最后由 piperacillin 于 2017-2-17 16:42 编辑

def ifprime(n):
k = 0
if n == 1 or n == 0:
k = 1
elif n % 2 == 0 and n != 2:
k = 1
else:
from math import sqrt
maxi = int(sqrt(n))
for i in range(3,maxi+1,2):
if n % i == 0:
k = 1
break
if k == 0:
return True
if k == 1:
return False
k = 0
for i in range(1,2000001):
if ifprime(i):
k +=i
print(k)

复制代码

0mrli0 · 发表于 2017-2-23 15:08:54

效率有点低

/*计算200万以内所有质数的和*/
#include <stdio.h>
#include <math.h>
int IsPrime(int x)
{
int i, flag;
flag = 1;
for (i=2; i<=(int)sqrt(x); i++)
{
if (x%i == 0)
{
flag = 0;
break;
}
}
return flag;
}
int main()
{
int i;
long long sum = 2;
for(i=3; i<=2000000; i+=2)
{
sum = IsPrime(i) ? sum + i : sum;
}
printf("sum = %lld", sum);
return 0;
}

复制代码

sum = 142913828922
Process returned 0 (0x0) execution time : 11.465 s

99592938 · 发表于 2017-3-14 18:00:03

import time
start = time.clock()
list_prime=[2,3]
s=num=5
while num<2000000:
f=1
for i in range(2,int(num**0.5)+1):
if num%i==0:
f=0
if f:
s+=num
num+=2
print(s)
end = time.clock()
print("read:%f s" %(end - start))

复制代码

卧槽，跑下来都4分多钟了
答案：>>>
142913828922
read:255.466301 s

JonTargaryen · 发表于 2017-3-30 14:30:06

本帖最后由 JonTargaryen 于 2017-3-30 14:51 编辑

秒出 142913828922

参考：http://blog.csdn.net/liukehua123/article/details/5482854

#include <stdio.h>
#include <math.h>
#define MAX 2000000
int is_prime(long num);
int main(void)
{
_Bool prime[MAX + 1] = {0};
long i = 3, j;
long sum = 2;
prime[2] = 1;
for(i = 3; i <= MAX; i += 2)
{
prime[i] = 1;
}
for(i = 3; i < sqrt(MAX); i += 2)
{
if(prime[i])
{
for(j = i + i; j <= MAX; j += i)
{
prime[j] = 0;
}
}
}
for(i = 3; i <= MAX; i += 2)
{
if(prime[i])
{
sum += i;
}
}
printf("The sum of all the primes within 2,000,000 is: %ld\n", sum);
return 0;
}
}

复制代码

JonTargaryen · 发表于 2017-3-30 15:06:46

本帖最后由 JonTargaryen 于 2017-3-30 15:11 编辑

JonTargaryen 发表于 2017-3-30 14:30
秒出 142913828922

参考：http://blog.csdn.net/liukehua123/article/details/5482854

python 慢一点 0.41595s

import math
MAX = 2000000
def main():
global MAX
prime = [0]
prime = prime * (MAX + 1)
num = 3
result = 2
prime[2] = 1
for num in range(3, MAX + 1, 2):
prime[num] = 1;
for num in range(3, int(math.sqrt(MAX) + 1), 2):
if prime[num]:
for j in range(num + num, MAX + 1, num):
prime[j] = 0
for num in range(3, MAX + 1, 2):
if prime[num]:
result += num
print(result)
if __name__ == "__main__":
main()

复制代码

Eagle.Tong · 发表于 2017-4-29 14:46:32

#求2百万一下所有质数的和

import math
import time
start = time.time()
def ifprime(n):
r = int(math.sqrt(n))
for i in range(2,r+1):
if n%i == 0:
return 0
return 1
sum = 2
n = 3
while n < 2000000:
if ifprime(n):
sum += n
n += 2
print(sum)
end = time.time()
print(end-start)

复制代码

结果：142913828922
时间：33.8529691696167

天之南 · 发表于 2017-5-1 00:46:51

本帖最后由天之南于 2017-5-1 01:18 编辑

##include<stdio.h>
int main()
{
const int L = 200000;
long long result = 5;
int arr[200000] = { 2,3 };
int i = 2;
for (int x = 5;i < L&&x < 2000000;x += 2)
{
int j;
for (j = 0;arr[j]* arr[j] <= x;j++)
{
if (x % arr[j] == 0)
{
j = 0;
break;
}
}
if (j)
{
arr[i] = x;
result += x;
i++;
}
}
system("pause");
return 0;
}

复制代码

天之南 · 发表于 2017-5-1 01:14:04

#include<stdio.h>
int main()
{
const int L = 200000;
long long result = 5;
int arr[200000] = { 2,3 };
int i = 2;
for (int x = 5;i < L&&x < 2000000;x += 2)
{
int j;
for (j = 0;arr[j]* arr[j] <= x;j++)
{
if (x % arr[j] == 0) {
j = 0;
break;
}
}
if (j) {
arr[i] = x;
result += x;
i++;
}
}
printf("%lld\n", result);
return 0;
}

复制代码

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