a1351468657 发表于 2021-3-6 18:35
time=1
两百万以内素数和为：143042032122
可以试下欧拉筛法, 参考一下49#
永恒的蓝色梦想 发表于 2021-3-7 23:44
可以试下欧拉筛法, 参考一下49#
好的，谢谢大佬！
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
#计算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 MAX2000000
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 于 2022-1-2 18:33 编辑
本题最快的算法是应用筛法。如果应用朴素的穷举法，在主机（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;
lm = 0;
int n = s + 2 * (threadIdx.x + blockIdx.x * nBlockDim);
if (n <= D)
{
if (isprime(n))
lm = n;
}
__syncthreads();
int k = nBlockDim / 2;
while (k > 0)
{
if (threadIdx.x < k)
lm += lm;
__syncthreads();
k /= 2;
}
if (threadIdx.x == 0)
r = lm;
}
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;
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;
}
#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);
}
209s{:5_104:}蚌埠住了
#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;
}
运行结果：
142915828922
It costs 0.376059 s
import time
import math
def euler_prime(num_range):
bool_prime = * (num_range-1)
for i in range(2, int(math.sqrt(num_range))):
if bool_prime:
for j in range(2, int(math.sqrt(i)) + 1):
if i % j == 0:
break
if bool_prime:
for k in range(i*i, num_range, i):
bool_prime = False
print(sum(i for i in range(2, num_range + 1) if bool_prime))
start = time.perf_counter()
euler_prime(2000000)
print('It costs %f s' % (time.perf_counter() - start))
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
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