论坛 › 欧拉计划（Project Euler） › 题目10：计算两百万以下所有质数的和

欧拉计划 发表于 2015-4-21 00:19:10

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

本帖最后由 不二如是 于 2017-6-11 22:38 编辑

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

题目：

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

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

牡丹花下死做鬼 发表于 2015-5-17 07:22:23

这不就是欧拉的题目么 谢谢翻译O(∩_∩)O哈！ 当时刚学C时我做了十多题 但是怎奈英语太烂翻译出来的 ........ 高考考完后我一定来捧场

翅膀团 发表于 2015-7-17 21:04:19

本帖最后由 翅膀团 于 2015-11-16 14:12 编辑

#include <stdio.h>
#define NUM 2000000

int main(void)
{
    int i,j,result=0;
   
    for(i=2;i<NUM;i++)
    {
    for(j=2;j<i;j++)
    {
    if(i % j ==0)
    {
    goto z;
    }   
    }
    result += i;
z:j=2;
    }
    printf("%d\n",result);
}

如果有错误希望指出

牡丹花下死做鬼 发表于 2015-7-19 21:59:46

翅膀团 发表于 2015-7-17 21:04
#include
#define NUM 2000000



printf("%d\n",result);
就看你这一句就知道肯定错

翅膀团 发表于 2015-7-20 15:20:16

牡丹花下死做鬼 发表于 2015-7-19 21:59
printf("%d\n",result);
就看你这一句就知道肯定错

还请指明哪里错了，这个办法虽然笨了点，慢了点，但还是能算出结果的

牡丹花下死做鬼 发表于 2015-7-21 08:11:50

翅膀团 发表于 2015-7-20 15:20
还请指明哪里错了，这个办法虽然笨了点，慢了点，但还是能算出结果的

你确定 int 装的下

翅膀团 发表于 2015-7-21 12:25:44

牡丹花下死做鬼 发表于 2015-7-21 08:11
你确定 int 装的下

你的机子int的范围我不知道，但我的机子的int是4字节，即-2147483648 ~ +2147483647 。2百万还是装得下的

mysteri0n 发表于 2016-1-24 13:36:04

本帖最后由 mysteri0n 于 2016-1-24 13:50 编辑

#python 2.7.11

def isprime(num):
    for i in range(2,int(num**0.5)+1):
      if num % i == 0:
            return False
    return True

print 2 + sum(num for num in xrange(3,2000000,2) if isprime(num))

ppsuc_wuj 发表于 2016-3-1 23:04:23

楼上的运行了半天出不来，效率太低了，这个秒出答案。判断质数的最快的方法。


int main()
{
    long i,j,gab=2,count,total=3,sum=10;
    long prime={2,3,5};
    for(i=7;i<2000000;i+=gab)
    {
      count=1;
      gab=6-gab;
      for(j=0;prime*prime<=i;j++)
      {
            if(i%prime==0)
            {
                count=0;
                break;
            }
      }
      if(count)
      {
            prime=i;
            total++;
            sum+=i;
      }
    }
    printf("%ld\n",sum);
}


答案142913828922

huomqh 发表于 2016-6-13 17:33:38

list1=
x=1
sum1=2
while x<=2000000:
    a=1
    x+=2
    for i in list1:
      if i**2>x:
            break
      if x%i==0:
            a=0
            break
    if a:
      sum1+=x
      list1.append(x)
print(sum1)


142913828922

purplenight 发表于 2016-8-7 08:03:32

# 修改自我的另一份代码, 部分代码或差劲, 能出结果就行.
time ./sum200
(p) 2
(p) 3
(p) 5
(p) 0
(p) 0
(next)(p) 148933
(prime p) 0
sum 142913828922.000000

real        0m0.685s
user        0m0.648s
sys        0m0.024s
#include <stdio.h>
#include <math.h>

#define LEN 2000000
int main(){
    static int prime = {2, 3, 5};
    static int num = {0, 0, 2, 3, 0, 5};
    int i, j;
    int p, root, found;
    double sum;

    for (i=0; i<5; i++) {
      printf("(p) %d\n", prime);
    }

    for (i=6; i<LEN;) {
      i++;
      num = i;
      i++;
    }

    for (i=6; i<LEN;) {
      i += 3;
      num = 0;
    }

    for (i=5; i<LEN;) {
      i += 5;
      num = 0;
    }

    p = 3;
    printf("(next)");
    for (i=7; i<LEN;i++) {
      if (num > 0) {
            root = (int)sqrt(num);
            for (j=3; j<root; j++) {
                if (prime > root ) {
                  found = 1;
                  break;
                }
                if (num % prime == 0) {
                  found = 0;
                  break;
                }
                else {
                  found = 1;
                }
            }
            if (found == 1) {
                prime = num;
                p++;
                if (p == LEN) {
                  break;
                }
            }
      }
    }

    printf("(p) %d\n", p);
    printf("(prime p) %d\n", prime);
    for (sum=0,i=0;i<LEN;i++){
      sum += prime;
    }
    printf("sum %lf\n", sum);
}

purplenight 发表于 2016-8-7 08:19:58

huomqh 发表于 2016-6-13 17:33
142913828922

time pypy prime.py
142913828922

real        0m1.345s
user        0m1.228s
sys        0m0.024s
time python2 prime.py
142913828922

real        0m20.487s
user        0m18.916s
sys        0m0.024s
time python3 prime.py
142913828922

real        0m52.103s
user        0m48.540s
sys        0m0.044s
pypy --version
Python 2.7.10 (5.3.1+dfsg-1, Jun 18 2016, 12:54:36)

python --version
Python 2.7.11
python3 --version
Python 3.5.2

purplenight 发表于 2016-8-7 08:35:45

ppsuc_wuj 发表于 2016-3-1 23:04
楼上的运行了半天出不来，效率太低了，这个秒出答案。判断质数的最快的方法。




time ./prime
142913828922.000000

real        0m0.614s
user        0m0.592s
sys        0m0.000s

purplenight 发表于 2016-8-7 09:14:58

mysteri0n 发表于 2016-1-24 13:36


$time pypy prime.py
142913828922

real        0m5.094s
user        0m4.712s
sys        0m0.016s
$time python2 prime.py
142913828922

real        0m58.416s
user        0m53.648s
sys        0m0.016s
$time python3 prime.py
142913828922

real        1m21.485s
user        1m19.448s
sys        0m0.024s

QingXin 发表于 2016-9-16 14:04:36

import math

def find_prime(max_x):
    prime_list =

    k = 9
    while k<max_x:
      total_yushu = 0
      square_root = math.sqrt(k)
      for each in prime_list:
            if each > square_root:
                break
            if k%each ==0:
                total_yushu = 1
                break
      if total_yushu == 0:
            prime_list.append(k)
      k+=2

    return prime_list

if __name__=='__main__':
    import timeit
    import math
    print(sum(find_prime(2000000)))
结果是142913828922

jerryxjr1220 发表于 2016-9-17 00:24:43

本帖最后由 jerryxjr1220 于 2016-10-10 16:34 编辑

def isPrime(n):
        if n == 2: return True
        elif n%2 == 0: return False
        elif (n-1)/6 != int((n-1)/6) or (n+1)/6 != int((n+1)/6): return False
        else:
                for i in range(3,int(n**0.5+1),2):
                        if n%i == 0: return False
                return True

cal, summ = 3, 2
while cal < 2000000:
        if isPrime(cal): summ += cal
        cal += 2
print summ

========================
142913828922

jerryxjr1220 发表于 2016-10-10 19:23:44

最快的求质数的方法：
142913828922


def getPrime(n):
        primes = *n
        primes,primes=False,False
        for (i, prime) in enumerate(primes):
                if prime:
                        for j in range(i*i,n,i): primes = False
        return

print (sum(getPrime(2000000)))

776667 发表于 2016-10-12 08:22:09

def is_prime(number):
    if number in :
      return False
    if number == 2:
      return True
    for i in range(2,int(number**0.5)+1):
      if not number%i:
            return False
    return True

def euler(x):
    return sum()

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

376103327 发表于 2016-10-26 19:22:38

本帖最后由 376103327 于 2016-10-26 19:25 编辑

import math
list1 = []
for i in range(2, 2000000+1):
    for j in range(2, int(math.sqrt(i))+1):
      if i % j == 0:
            break
    else:
      print i
      list1.append(i)
print sum(list1)

tsembrace 发表于 2016-11-11 22:38:58

#找出两百万以下所有质数的和
import math
import time

def isPrime(n):
    if n<2:
      return False
    elif n==2:
      return True
    else:
      m=int(math.sqrt(n))
      for i in range(2,m+1):
            if n%i==0:
                return False
      return True

def primeSum(n):
    s=0
    for i in range(1,n):
      if isPrime(i):
            s+=i
    return s

start=time.clock()

print("两百万以内的质数之和为："+str(primeSum(2000000)))

end=time.clock()

print("耗时："+str(end-start)+"秒")

查看完整版本: 题目10：计算两百万以下所有质数的和