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

梦想绘制者

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

梦想绘制者

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

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

梦想绘制者

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

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

jerryxjr1220

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

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

梦想绘制者

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

lyciam

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-16 08:54
谢谢，这是以空间换时间的好方法啊，可以进一步优化的，先判断奇偶性，偶数不存储只判断奇数。哈哈，网上看 ...

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

梦想绘制者

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

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

芒果加黄桃

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

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

芒果加黄桃

# 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

渡风

此代码使用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

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

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

效率有点低

/*计算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

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

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

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

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

天之南

##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;
}

天之南

#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;
}