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

永恒的蓝色梦想

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

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

a1351468657

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

好的，谢谢大佬！

Kuri5u

result=[]
for num in range(2,2000001):
    for each in range(2,int(num**0.5)+1):
        if num % each==0:
            break
    else:
        result.append(num)

print(sum(result))

卢本伟牛逼

#include <stdio.h>
#include <math.h>

static int count;

int is_prime(int value)
{
        int j;
        if (value == 2) return 1;
        for(j=2; j<sqrt(value)+1; j++){
                count += 1;
                if (j>3) j++;
                if (value%j==0) return 0;
        }
        return 1;
}

int main(void) 
{
        long long int sum = 0;
        int i;
        
        for(i = 2; i<=2000000; i++)
        {
                if (is_prime(i)) sum+=i;
        }
        
        printf("sum = %lld\n", sum);
        printf("count = %d\n", count);
        
        return 0;
}
//sum = 142913828922
//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  

番杰

#include<stdio.h>

#define MAX  2000000

int main(void)
{
        unsigned int sum = 2; 
        
        for(int i = 2;i < MAX;i++)
        {
                for(int j = 2;j < (i / 2);j++)
                {
                        if(i % j == 0)
                        {
                                flag = 1;
                                break;
                        }
                        else
                                flag = 0;
                }
                if(flag == 0)                
                        sum += i;        
        }
        
        printf("%d",sum);
        
        return 0;
}

弈秋呜呜呜

0.8秒 答案142913828922

#include <stdio.h>
#include <math.h>

void main(void)
{
        long long sum = 0;
        long i,j,temp;
        
        for (i = 2;i < 2000000;i++)
        {
                temp = sqrt(i);
                for (j = 2;j <= temp;j++)
                {
                        if (i % j == 0)
                                break;
                }
                if (j > temp)
                        sum += i;
        }
        printf("%lld\n",sum);
}

guosl

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

/*
答案：142913828922
耗时：0.014134（GTX970）
*/
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>

const int D = 2000000;
const int nBlockDim = 128;
const int nBlocks = 128;

__device__ bool isprime(int n)
{
  if ((n & 1) == 0)
    return false;
  int d = (int)sqrt((double)n);
  for (int i = 3; i <= d; i += 2)
  {
    if ((n % i) == 0)
      return false;
  }
  return true;
}

__global__ void findprime(int s, int* r)
{
  __shared__ int lm[nBlockDim];
  lm[threadIdx.x] = 0;
  int n = s + 2 * (threadIdx.x + blockIdx.x * nBlockDim);
  if (n <= D)
  {
    if (isprime(n))
      lm[threadIdx.x] = n;
  }
  __syncthreads();
  int k = nBlockDim / 2;
  while (k > 0)
  {
    if (threadIdx.x < k)
      lm[threadIdx.x] += lm[threadIdx.x + k];
    __syncthreads();
    k /= 2;
  }
  if (threadIdx.x == 0)
    r[blockIdx.x] = lm[0];
}

int main(void)
{
  int* pM = NULL;
  int* p_dM = NULL;
  int s = 3;
  long long nSum = 2;
  cudaError_t cudaStatus;
  int nPId = 0;
  cudaStatus = cudaSetDevice(nPId);//设置计算卡
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "cudaSetDevice failed!  Do you have a CUDA-capable GPU installed?");
    goto Error;
  }
  cudaDeviceProp deviceProp;
  cudaGetDeviceProperties(&deviceProp, nPId);
  printf("GPU Device %d: "%s" with compute capability %d.%d\n\n",
    nPId, deviceProp.name, deviceProp.major, deviceProp.minor);
  //在显卡上分配内存
  cudaStatus = cudaSetDevice(0);
  cudaStatus = cudaHostAlloc((void**)&pM, nBlocks * sizeof(int), cudaHostAllocDefault);
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "CUDA alloc memory failed!");
    goto Error;
  }
  cudaStatus = cudaMalloc((void**)&p_dM, nBlocks * sizeof(int));
  if (cudaStatus != cudaSuccess)
  {
    fprintf(stderr, "cudaMalloc failed!");
    goto Error;
  }
  while (s <= D)
  {
    findprime << <nBlocks, nBlockDim >> > (s, p_dM);
    cudaDeviceSynchronize();
    cudaMemcpy(pM, p_dM, nBlocks * sizeof(int), cudaMemcpyDeviceToHost);
    for (int i = 0; i < nBlocks; ++i)
      nSum += pM[i];
    s += 2 * nBlocks * nBlockDim;
  }
  printf("%lld\n", nSum);
Error:
  if (p_dM != NULL)
  {
    cudaFree(p_dM);
    p_dM = NULL;
  }
  if (pM != NULL)
  {
    cudaFreeHost(pM);
    pM = NULL;
  }
  return 0;
}

mathtimes

#include <stdio.h>
#include <vector>
using std::vector;
int main()
{
    vector<long long> prime;
    vector<long long>::iterator it;
    long long i,sum = 2;   
    prime.push_back(2);
    for(i=2;i<2e6;i++)
    {
        for(it=prime.begin();it!=prime.end();it++)
        {
            if(i%*it==0)
                goto loop;
        }
        prime.push_back(i);
        sum += i; 
        loop:;
    }         
    printf("%lld",sum);
}

Kazimierz

209s蚌埠住了

#include <stdio.h>
#define NUM 2000000

int main()
{
        int i,n=0,x=3;
        unsigned long long int result=2,s=1;

        while(x<NUM)
        {
                for(i=2;i<x;i++)
                {
                        if(x%i==0){
                                n++;
                                x++;
                                break;
                        }
                }
                
                if(n==0){
                        result+=x;
                        s++;
                        x++;
                        continue;
                }
                
                n=0;
        }
        printf("%lld",result);
        return 0;
        
}

B1tetheDust

运行结果：
142915828922
It costs 0.376059 s

import time
import math


def euler_prime(num_range):
    bool_prime = [True] * (num_range-1)
    for i in range(2, int(math.sqrt(num_range))):
        if bool_prime[i-2]:
            for j in range(2, int(math.sqrt(i)) + 1):
                if i % j == 0:
                    break
        if bool_prime[i-2]:
            for k in range(i*i, num_range, i):
                bool_prime[k - 2] = False
    print(sum(i for i in range(2, num_range + 1) if bool_prime[i-2]))


start = time.perf_counter()
euler_prime(2000000)
print('It costs %f s' % (time.perf_counter() - start))

Asss-whom

use rayon::prelude::*;
use std::time::Instant;

const N: i64 = 2000000;

fn main() {
    let now = Instant::now();
    let mut primes = Vec::new();
    let mut cur = 10;
    // bootstrap
    for i in 2..cur {
        if primes.iter().all(|p| i % p != 0) {
            primes.push(i);
        }
    }
    while cur < N {
        let next = std::cmp::min(cur * cur, N);
        let mut addition: Vec<_> = (cur..next)
            .into_par_iter()
            .filter(|x| {
                for p in primes.iter() {
                    if x % p == 0 {
                        return false;
                    }
                    if x / p < *p {
                        break;
                    }
                }
                true
            })
            .collect();
        primes.append(&mut addition);
        cur = next;
    }
    let num: i64 = primes.into_par_iter().sum();
    println!("cost {} ms.", now.elapsed().as_millis());
    println!("{}", num)
}

---
cost 22 ms.
142913828922

qingyunvi

import time
start = time.time()


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


total = 0
for i in range(1, 2000000):
    if is_prime(i):
        total += i

print(total)


end = time.time()
print(f'time:{end - start}')

142913828922
time:13.038543701171875