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

永恒的蓝色梦想

a1351468657 发表于 2021-3-6 18:35
time=1
两百万以内素数和为：143042032122

可以试下欧拉筛法, 参考一下49#

a1351468657

永恒的蓝色梦想 发表于 2021-3-7 23:44
可以试下欧拉筛法, 参考一下49#

好的，谢谢大佬！

Kuri5u

1. result=[]
   
2. for num in range(2,2000001):
   
3.     for each in range(2,int(num**0.5)+1):
   
4.         if num % each==0:
   
5.             break
   
6.     else:
   
7.         result.append(num)
   
8. 
   
9. print(sum(result))
   

复制代码

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. static int count;
   
5. 
   
6. int is_prime(int value)
   
7. {
   
8.         int j;
   
9.         if (value == 2) return 1;
   
10.         for(j=2; j<sqrt(value)+1; j++){
    
11.                 count += 1;
    
12.                 if (j>3) j++;
    
13.                 if (value%j==0) return 0;
    
14.         }
    
15.         return 1;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         long long int sum = 0;
    
21.         int i;
    
22.        
    
23.         for(i = 2; i<=2000000; i++)
    
24.         {
    
25.                 if (is_prime(i)) sum+=i;
    
26.         }
    
27.        
    
28.         printf("sum = %lld\n", sum);
    
29.         printf("count = %d\n", count);
    
30.        
    
31.         return 0;
    
32. }
    
33. //sum = 142913828922
    
34. //count = 91357987

复制代码

ft215378

#计算2百万之内的素数之和
import math
#判断是否是素数
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for a in range(3,int(math.sqrt(number) + 1),2):
            if number % a == 0:
                return False
        return True
    return False
   
#生成器(返回素数)
def get_prime(number):
    while True:
        if is_prime(number):
            yield number
        number += 1

#求和
def result():
    result = 2
    for next_prime in get_prime(3):
        if next_prime < 10:
            result += next_prime
        else:
            print(result)
            return  

番杰

1. #include<stdio.h>
   
2. 
   
3. #define MAX  2000000
   
4. 
   
5. int main(void)
   
6. {
   
7.         unsigned int sum = 2;
   
8.        
   
9.         for(int i = 2;i < MAX;i++)
   
10.         {
    
11.                 for(int j = 2;j < (i / 2);j++)
    
12.                 {
    
13.                         if(i % j == 0)
    
14.                         {
    
15.                                 flag = 1;
    
16.                                 break;
    
17.                         }
    
18.                         else
    
19.                                 flag = 0;
    
20.                 }
    
21.                 if(flag == 0)               
    
22.                         sum += i;       
    
23.         }
    
24.        
    
25.         printf("%d",sum);
    
26.        
    
27.         return 0;
    
28. }

复制代码

弈秋呜呜呜

0.8秒 答案142913828922

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. void main(void)
   
5. {
   
6.         long long sum = 0;
   
7.         long i,j,temp;
   
8.        
   
9.         for (i = 2;i < 2000000;i++)
   
10.         {
    
11.                 temp = sqrt(i);
    
12.                 for (j = 2;j <= temp;j++)
    
13.                 {
    
14.                         if (i % j == 0)
    
15.                                 break;
    
16.                 }
    
17.                 if (j > temp)
    
18.                         sum += i;
    
19.         }
    
20.         printf("%lld\n",sum);
    
21. }

复制代码

guosl

本题最快的算法是应用筛法。如果应用朴素的穷举法，在主机（CPU）上运行的时间基本上都在0.1秒左右。但如果用GPU进行编程则我们可以得到眼前一亮的结果。

1. /*
   
2. 答案：142913828922
   
3. 耗时：0.014134（GTX970）
   
4. */
   
5. #include "cuda_runtime.h"
   
6. #include "device_launch_parameters.h"
   
7. #include <stdio.h>
   
8. 
   
9. const int D = 2000000;
   
10. const int nBlockDim = 128;
    
11. const int nBlocks = 128;
    
12. 
    
13. __device__ bool isprime(int n)
    
14. {
    
15.   if ((n & 1) == 0)
    
16.     return false;
    
17.   int d = (int)sqrt((double)n);
    
18.   for (int i = 3; i <= d; i += 2)
    
19.   {
    
20.     if ((n % i) == 0)
    
21.       return false;
    
22.   }
    
23.   return true;
    
24. }
    
25. 
    
26. __global__ void findprime(int s, int* r)
    
27. {
    
28.   __shared__ int lm[nBlockDim];
    
29.   lm[threadIdx.x] = 0;
    
30.   int n = s + 2 * (threadIdx.x + blockIdx.x * nBlockDim);
    
31.   if (n <= D)
    
32.   {
    
33.     if (isprime(n))
    
34.       lm[threadIdx.x] = n;
    
35.   }
    
36.   __syncthreads();
    
37.   int k = nBlockDim / 2;
    
38.   while (k > 0)
    
39.   {
    
40.     if (threadIdx.x < k)
    
41.       lm[threadIdx.x] += lm[threadIdx.x + k];
    
42.     __syncthreads();
    
43.     k /= 2;
    
44.   }
    
45.   if (threadIdx.x == 0)
    
46.     r[blockIdx.x] = lm[0];
    
47. }
    
48. 
    
49. int main(void)
    
50. {
    
51.   int* pM = NULL;
    
52.   int* p_dM = NULL;
    
53.   int s = 3;
    
54.   long long nSum = 2;
    
55.   cudaError_t cudaStatus;
    
56.   int nPId = 0;
    
57.   cudaStatus = cudaSetDevice(nPId);//设置计算卡
    
58.   if (cudaStatus != cudaSuccess)
    
59.   {
    
60.     fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
    
61.     goto Error;
    
62.   }
    
63.   cudaDeviceProp deviceProp;
    
64.   cudaGetDeviceProperties(&deviceProp, nPId);
    
65.   printf("GPU Device %d: "%s" with compute capability %d.%d\n\n",
    
66.     nPId, deviceProp.name, deviceProp.major, deviceProp.minor);
    
67.   //在显卡上分配内存
    
68.   cudaStatus = cudaSetDevice(0);
    
69.   cudaStatus = cudaHostAlloc((void**)&pM, nBlocks * sizeof(int), cudaHostAllocDefault);
    
70.   if (cudaStatus != cudaSuccess)
    
71.   {
    
72.     fprintf(stderr, "CUDA alloc memory failed!");
    
73.     goto Error;
    
74.   }
    
75.   cudaStatus = cudaMalloc((void**)&p_dM, nBlocks * sizeof(int));
    
76.   if (cudaStatus != cudaSuccess)
    
77.   {
    
78.     fprintf(stderr, "cudaMalloc failed!");
    
79.     goto Error;
    
80.   }
    
81.   while (s <= D)
    
82.   {
    
83.     findprime << <nBlocks, nBlockDim >> > (s, p_dM);
    
84.     cudaDeviceSynchronize();
    
85.     cudaMemcpy(pM, p_dM, nBlocks * sizeof(int), cudaMemcpyDeviceToHost);
    
86.     for (int i = 0; i < nBlocks; ++i)
    
87.       nSum += pM[i];
    
88.     s += 2 * nBlocks * nBlockDim;
    
89.   }
    
90.   printf("%lld\n", nSum);
    
91. Error:
    
92.   if (p_dM != NULL)
    
93.   {
    
94.     cudaFree(p_dM);
    
95.     p_dM = NULL;
    
96.   }
    
97.   if (pM != NULL)
    
98.   {
    
99.     cudaFreeHost(pM);
    
100.     pM = NULL;
     
101.   }
     
102.   return 0;
     
103. }
     

复制代码

mathtimes

1. #include <stdio.h>
   
2. #include <vector>
   
3. using std::vector;
   
4. int main()
   
5. {
   
6.     vector<long long> prime;
   
7.     vector<long long>::iterator it;
   
8.     long long i,sum = 2;   
   
9.     prime.push_back(2);
   
10.     for(i=2;i<2e6;i++)
    
11.     {
    
12.         for(it=prime.begin();it!=prime.end();it++)
    
13.         {
    
14.             if(i%*it==0)
    
15.                 goto loop;
    
16.         }
    
17.         prime.push_back(i);
    
18.         sum += i;
    
19.         loop:;
    
20.     }         
    
21.     printf("%lld",sum);
    
22. }

复制代码

Kazimierz

209s蚌埠住了

1. #include <stdio.h>
   
2. #define NUM 2000000
   
3. 
   
4. int main()
   
5. {
   
6.         int i,n=0,x=3;
   
7.         unsigned long long int result=2,s=1;
   
8. 
   
9.         while(x<NUM)
   
10.         {
    
11.                 for(i=2;i<x;i++)
    
12.                 {
    
13.                         if(x%i==0){
    
14.                                 n++;
    
15.                                 x++;
    
16.                                 break;
    
17.                         }
    
18.                 }
    
19.                
    
20.                 if(n==0){
    
21.                         result+=x;
    
22.                         s++;
    
23.                         x++;
    
24.                         continue;
    
25.                 }
    
26.                
    
27.                 n=0;
    
28.         }
    
29.         printf("%lld",result);
    
30.         return 0;
    
31.        
    
32. }

复制代码

B1tetheDust

运行结果：
142915828922
It costs 0.376059 s

1. import time
   
2. import math
   
3. 
   
4. 
   
5. def euler_prime(num_range):
   
6.     bool_prime = [True] * (num_range-1)
   
7.     for i in range(2, int(math.sqrt(num_range))):
   
8.         if bool_prime[i-2]:
   
9.             for j in range(2, int(math.sqrt(i)) + 1):
   
10.                 if i % j == 0:
    
11.                     break
    
12.         if bool_prime[i-2]:
    
13.             for k in range(i*i, num_range, i):
    
14.                 bool_prime[k - 2] = False
    
15.     print(sum(i for i in range(2, num_range + 1) if bool_prime[i-2]))
    
16. 
    
17. 
    
18. start = time.perf_counter()
    
19. euler_prime(2000000)
    
20. print('It costs %f s' % (time.perf_counter() - start))

复制代码

Asss-whom

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. const N: i64 = 2000000;
   
5. 
   
6. fn main() {
   
7.     let now = Instant::now();
   
8.     let mut primes = Vec::new();
   
9.     let mut cur = 10;
   
10.     // bootstrap
    
11.     for i in 2..cur {
    
12.         if primes.iter().all(|p| i % p != 0) {
    
13.             primes.push(i);
    
14.         }
    
15.     }
    
16.     while cur < N {
    
17.         let next = std::cmp::min(cur * cur, N);
    
18.         let mut addition: Vec<_> = (cur..next)
    
19.             .into_par_iter()
    
20.             .filter(|x| {
    
21.                 for p in primes.iter() {
    
22.                     if x % p == 0 {
    
23.                         return false;
    
24.                     }
    
25.                     if x / p < *p {
    
26.                         break;
    
27.                     }
    
28.                 }
    
29.                 true
    
30.             })
    
31.             .collect();
    
32.         primes.append(&mut addition);
    
33.         cur = next;
    
34.     }
    
35.     let num: i64 = primes.into_par_iter().sum();
    
36.     println!("cost {} ms.", now.elapsed().as_millis());
    
37.     println!("{}", num)
    
38. }
    

复制代码

---
cost 22 ms.
142913828922

qingyunvi

1. import time
   
2. start = time.time()
   
3. 
   
4. 
   
5. def is_prime(n):
   
6.     if n <= 1:
   
7.         return False
   
8.     for i in range(2, int(n ** 0.5) + 1):
   
9.         if n % i == 0:
   
10.             return False
    
11.     return True
    
12. 
    
13. 
    
14. total = 0
    
15. for i in range(1, 2000000):
    
16.     if is_prime(i):
    
17.         total += i
    
18. 
    
19. print(total)
    
20. 
    
21. 
    
22. end = time.time()
    
23. print(f'time:{end - start}')

复制代码

142913828922
time:13.038543701171875