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

欧拉计划

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。

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

牡丹花下死做鬼

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

翅膀团

#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-17 21:04
#include
#define NUM 2000000

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

翅膀团

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

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

牡丹花下死做鬼

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

你确定 int 装的下

翅膀团

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

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

mysteri0n

1. #python 2.7.11
   
2. 
   
3. def isprime(num):
   
4.     for i in range(2,int(num**0.5)+1):
   
5.         if num % i == 0:
   
6.             return False
   
7.     return True
   
8. 
   
9. print 2 + sum(num for num in xrange(3,2000000,2) if isprime(num))
   

复制代码

ppsuc_wuj

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


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


答案  142913828922

huomqh

1. list1=[2]
   
2. x=1
   
3. sum1=2
   
4. while x<=2000000:
   
5.     a=1
   
6.     x+=2
   
7.     for i in list1:
   
8.         if i**2>x:
   
9.             break
   
10.         if x%i==0:
    
11.             a=0
    
12.             break
    
13.     if a:
    
14.         sum1+=x
    
15.         list1.append(x)
    
16. print(sum1)
    

复制代码

142913828922

purplenight

# 修改自我的另一份代码, 部分代码或差劲, 能出结果就行.

1. time ./sum200
   
2. (p) 2
   
3. (p) 3
   
4. (p) 5
   
5. (p) 0
   
6. (p) 0
   
7. (next)(p) 148933
   
8. (prime p) 0
   
9. sum 142913828922.000000
   
10. 
    
11. real        0m0.685s
    
12. user        0m0.648s
    
13. sys        0m0.024s

复制代码

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define LEN 2000000
   
5. int main(){
   
6.     static int prime[LEN] = {2, 3, 5};
   
7.     static int num[LEN] = {0, 0, 2, 3, 0, 5};
   
8.     int i, j;
   
9.     int p, root, found;
   
10.     double sum;
    
11. 
    
12.     for (i=0; i<5; i++) {
    
13.         printf("(p) %d\n", prime[i]);
    
14.     }
    
15. 
    
16.     for (i=6; i<LEN;) {
    
17.         i++;
    
18.         num[i] = i;
    
19.         i++;
    
20.     }
    
21. 
    
22.     for (i=6; i<LEN;) {
    
23.         i += 3;
    
24.         num[i] = 0;
    
25.     }
    
26. 
    
27.     for (i=5; i<LEN;) {
    
28.         i += 5;
    
29.         num[i] = 0;
    
30.     }
    
31. 
    
32.     p = 3;
    
33.     printf("(next)");
    
34.     for (i=7; i<LEN;i++) {
    
35.         if (num[i] > 0) {
    
36.             root = (int)sqrt(num[i]);
    
37.             for (j=3; j<root; j++) {
    
38.                 if (prime[j] > root ) {
    
39.                     found = 1;
    
40.                     break;
    
41.                 }
    
42.                 if (num[i] % prime[j] == 0) {
    
43.                     found = 0;
    
44.                     break;
    
45.                 }
    
46.                 else {
    
47.                     found = 1;
    
48.                 }
    
49.             }
    
50.             if (found == 1) {
    
51.                 prime[p] = num[i];
    
52.                 p++;
    
53.                 if (p == LEN) {
    
54.                     break;
    
55.                 }
    
56.             }
    
57.         }
    
58.     }
    
59. 
    
60.     printf("(p) %d\n", p);
    
61.     printf("(prime p) %d\n", prime[p]);
    
62.     for (sum=0,i=0;i<LEN;i++){
    
63.         sum += prime[i];
    
64.     }
    
65.     printf("sum %lf\n", sum);
    
66. }

复制代码

purplenight

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

1. time pypy prime.py
   
2. 142913828922
   
3. 
   
4. real        0m1.345s
   
5. user        0m1.228s
   
6. sys        0m0.024s
   
7. time python2 prime.py
   
8. 142913828922
   
9. 
   
10. real        0m20.487s
    
11. user        0m18.916s
    
12. sys        0m0.024s
    
13. time python3 prime.py
    
14. 142913828922
    
15. 
    
16. real        0m52.103s
    
17. user        0m48.540s
    
18. sys        0m0.044s
    
19. pypy --version
    
20. Python 2.7.10 (5.3.1+dfsg-1, Jun 18 2016, 12:54:36)
    
21. [PyPy 5.3.1 with GCC 5.4.0 20160609]
    
22. python --version
    
23. Python 2.7.11
    
24. python3 --version
    
25. Python 3.5.2

复制代码

purplenight

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

1. time ./prime
   
2. 142913828922.000000
   
3. 
   
4. real        0m0.614s
   
5. user        0m0.592s
   
6. sys        0m0.000s

复制代码

purplenight

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

1. $  time pypy prime.py
   
2. 142913828922
   
3. 
   
4. real        0m5.094s
   
5. user        0m4.712s
   
6. sys        0m0.016s
   
7. $  time python2 prime.py
   
8. 142913828922
   
9. 
   
10. real        0m58.416s
    
11. user        0m53.648s
    
12. sys        0m0.016s
    
13. $  time python3 prime.py
    
14. 142913828922
    
15. 
    
16. real        1m21.485s
    
17. user        1m19.448s
    
18. sys        0m0.024s

复制代码

QingXin

1. import math
   
2. 
   
3. def find_prime(max_x):
   
4.     prime_list = [2,3,5,7]
   
5. 
   
6.     k = 9
   
7.     while k<max_x:
   
8.         total_yushu = 0
   
9.         square_root = math.sqrt(k)
   
10.         for each in prime_list:
    
11.             if each > square_root:
    
12.                 break
    
13.             if k%each ==0:
    
14.                 total_yushu = 1
    
15.                 break
    
16.         if total_yushu == 0:
    
17.             prime_list.append(k)
    
18.         k+=2
    
19. 
    
20.     return prime_list
    
21. 
    
22. if __name__=='__main__':
    
23.     import timeit
    
24.     import math
    
25.     print(sum(find_prime(2000000)))

复制代码

结果是142913828922

jerryxjr1220

1. def isPrime(n):
   
2.         if n == 2: return True
   
3.         elif n%2 == 0: return False
   
4.         elif (n-1)/6 != int((n-1)/6) or (n+1)/6 != int((n+1)/6): return False
   
5.         else:
   
6.                 for i in range(3,int(n**0.5+1),2):
   
7.                         if n%i == 0: return False
   
8.                 return True
   
9. 
   
10. cal, summ = 3, 2
    
11. while cal < 2000000:
    
12.         if isPrime(cal): summ += cal
    
13.         cal += 2
    
14. print summ
    
15. 
    
16. ========================
    
17. 142913828922
    
18. [Finished in 9.7s]

复制代码

jerryxjr1220

最快的求质数的方法：
142913828922
[Finished in 1.8s]

1. def getPrime(n):
   
2.         primes = [True]*n
   
3.         primes[0],primes[1]=False,False
   
4.         for (i, prime) in enumerate(primes):
   
5.                 if prime:
   
6.                         for j in range(i*i,n,i): primes[j] = False
   
7.         return [k for (k,trueprime) in enumerate(primes) if trueprime]
   
8. 
   
9. print (sum(getPrime(2000000)))

复制代码

776667

1. def is_prime(number):
   
2.     if number in [0,1]:
   
3.         return False
   
4.     if number == 2:
   
5.         return True
   
6.     for i in range(2,int(number**0.5)+1):
   
7.         if not number%i:
   
8.             return False
   
9.     return True
   
10. 
    
11. def euler(x):
    
12.     return sum([y for y in range(x+1) if is_prime(y)])
    
13. 
    
14. if __name__ == '__main__':
    
15.     print(euler(2000000))

复制代码

376103327

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

1. #找出两百万以下所有质数的和
   
2. import math
   
3. import time
   
4. 
   
5. def isPrime(n):
   
6.     if n<2:
   
7.         return False
   
8.     elif n==2:
   
9.         return True
   
10.     else:
    
11.         m=int(math.sqrt(n))
    
12.         for i in range(2,m+1):
    
13.             if n%i==0:
    
14.                 return False
    
15.         return True
    
16. 
    
17. def primeSum(n):
    
18.     s=0
    
19.     for i in range(1,n):
    
20.         if isPrime(i):
    
21.             s+=i
    
22.     return s
    
23. 
    
24. start=time.clock()
    
25. 
    
26. print("两百万以内的质数之和为："+str(primeSum(2000000)))
    
27. 
    
28. end=time.clock()
    
29. 
    
30. print("耗时："+str(end-start)+"秒")
    
31. 
    
32. 
    
33. 
    

复制代码