题目10：计算两百万以下所有质数的和,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

ruharley 发表于 2017-6-27 17:15:20

我使用的是matlab

% 素数的和
% 所有小于10的素数的和是2 + 3 + 5 + 7 = 17。
% 求所有小于两百万的素数的和。
tic
a=2000000;
A=2:a;
a=floor(sqrt(a));
B=2:a;
k=1;
n=length(B);
while k<=n
A=[B(k),A(mod(A,B(k))~=0)];
B=A(A<=a);
k=k+1;
n=length(B);
end
Sum=sum(A);
fprintf('小于两百万的素数的和%d\n',Sum)
toc

结果：
>>E10
小于两百万的素数的和142913828922
时间已过 2.334297 秒。

幻世伽蓝 发表于 2017-7-1 20:34:01

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

int zs(int n)
{
int i;
for(i=2;i<=(int)sqrt(n);i++)
{
   if(n%i==0)
         return 0;
}
return n;
}

int main()
{
long long sum = 2;
int i = 3;
for(;i<2000000;)
{
   if(zs(i))
   {
         sum += i;
   }
   i+=2;
}
printf("%lld",sum);
return 0;
}

改了好久，终于出来了{:10_266:}

BngThea 发表于 2017-9-12 13:58:50

total = 0
for n in range(2, int(2e6)):
for i in range(2,n//2+1):
   if not n % i:
         n = 0
         break
total += n

print(total)

发表于 2018-3-7 22:35:41

本帖最后由永恒的蓝色梦想于 2020-6-20 11:48 编辑

#include<stdio.h>
#include<math.h>
int main()
{
int i,j,tag=1;
double sum=0;
for(i=2;i<2000000;i++)
{
for(j=2;j<=sqrt(i);j++)
{
if(0==i%j)
{
tag=0;
break;
}
}
if(1==tag)
{
sum=sum+i;
}
tag=1;
}
printf("%.0lf\n",sum);
return 0;
}

refracted_ray 发表于 2018-4-15 11:35:11

import math

# 判断n是否质数
def prime(n):
flag=True # flag=True表示n是质数，False表示n是合数
# 当n=2时本应分开讨论，但因为flag一开始就是True，所以不影响结果
for i in range(2,int(math.sqrt(n))+1):
# 任意一个数能整除n，则n是合数
if n%i==0:
flag=False
break
if flag:
return True # n是质数则返回True
else:
return False # n是合数则返回False

# n从3开始，n=2直接预先放入p[]，这样n+2以去掉所有大于2的偶数
p=
n=3
while n<=2000000:
if prime(n):
p.append(n)
n+=2
print('2百万以内有%d个质数，它们的和是%d' %(len(p),sum(p)))

输出结果是
2百万以内有148933个质数，它们的和是142913828922

山有扶苏啊 发表于 2018-10-15 09:14:32

from math import sqrt

def is_prime(x):
if x==1:
   return False
for i in range(2, int(sqrt(x)) + 1):
   if x%i == 0:
         return False
return True

s = 0
for t in range(1, 2000000):
if is_prime(t):
   s = s+t
print(s)

142913828922

愿你发表于 2019-3-15 20:11:46

#include <stdio.h>
#include <math.h>
int isprime(int x)
{
long long int i;
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
return 0;
}
}
return 1;

}
main()
{
long long i,sum;
sum=0;
for(i=2;i<2000000;i++)
{
if(isprime(i))
sum=sum+i;
}
printf("%lld",sum);
}

王小召 发表于 2019-4-10 15:00:20

运行结果：142913828922
运行时间：12.464479899999999（速度很慢，算法需要优化）
import math
import time

def isprime(num):
num_s = int(math.sqrt(num))
for i in range(2, num_s + 1):
   if num % i == 0:
         return 0
         break
return num

def get_sum(max):
sum = 0
for x in range(2, max):
   sum += isprime(x)
return sum

print(get_sum(2000000))
print(time.process_time())

永恒的蓝色梦想 发表于 2019-8-3 20:29:32

本帖最后由永恒的蓝色梦想于 2021-2-20 20:47 编辑

C++ 11ms#include<iostream>
#include<vector>
#include<array>

int main() {
using namespace std;
ios::sync_with_stdio(false);

constexpr unsigned int UPPER_BOUND = 2000000;
static array<bool, UPPER_BOUND> is_prime;
vector<unsigned int> primes;
unsigned long long result = 0;
unsigned int i, k;
is_prime.fill(true);
is_prime = is_prime = 0;

for (i = 2; i < UPPER_BOUND; i++) {
   if (is_prime) {
         primes.push_back(i);
         result += i;
   }

   for (unsigned int j : primes) {
         k = i * j;

         if (k >= UPPER_BOUND) {
            break;
         }

         is_prime = false;

         if (!(i % j)) {
            break;
         }
   }
}

cout << result << endl;
return 0;
}

1666194196 发表于 2019-10-10 09:15:20

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

void main(){
//素数的和
//所有小于10的素数的和是 2 + 3 + 5 + 7 = 17。
//求所有小于两百万的素数的和。142913828922
long long i,j,sum=0;
int flag;
for(i=2;i<2000000;i++){//2为最小质数
printf("i=%d\n",i);
flag=1;
for(j=2;j<=sqrt(i);j++){//2到根号本身的循环用来找是否有能整除的数，有则不是质数
if(i%j==0){
flag=0;//不是质数，所以不加 ,if(flag)不执行
break;//找到 1个因数，就不是质数了，所以没必要在执行，跳出 j的 for循环
}
}
if(flag){
sum+=i;
}
}
printf("sum=%lld",sum);

}

foxiangzun 发表于 2019-11-5 21:01:47

实在想不出好办法，只能用蠢办法了。。看来得先去把数学课好好再上上。。

list1 = []
for i in range(2, 2000000) :
   flag = 0
   for j in range(2, int(i ** 0.5) + 1) :
            if i % j == 0 :
                     flag += 1
   if flag < 1 :
            list1.append(i)
            print(i)
print(sum(list1))

有理由相信 发表于 2020-2-10 19:53:32

t = int(input('不就是找素数嘛！输入范围直接开始吧'))
num =
n = []
a = 0
while a <= t:
n.append (a)
a = a + 1
a = 2
i = 2
while i <= t - 1:
f = 1
i = i + 1
if n == 0:
   continue
for k in num:
   if k > i**0.5:
         break
   elif i % k == 0:
         n = 0
         f = 0
         break
if f == 1:
   num.append (i)
   a = a + i
   k = 1
   while k <= i**i:
         if i**k > t:
            break
         for l in num:
            if l*i**k > t:
               break
            n = 0
         k = k + 1
print("所有素数和为")
print(str(a))
这是我以前编的，我觉得效率挺高

代号-K 发表于 2020-3-12 19:34:58

void calculatePrimeSum(ElementType value, ElementType *answer)
{
ElementType array = {0};
*answer = 2;
array = 2;
int i = 1;
int j = 3;
int k = 0;
bool yes = true;
while(true)
{
   if(j > value)
   {
         break;
   }
   else
   {
         k = 0;
         while( k < i)
         {
            if(j % array == 0)
            {
               yes = false;
               break;
            }
            k++;
         }
         // join answer
         if(yes)
         {
            *answer += j;
            array = j;
         }
   }
   j += 2;
   yes = true;
}
}

int main(int argc, char *argv[])
{
ElementTyperet;
calculatePrimeSum(200000, &ret);
printf("%lld\n", ret);
return 0;
}

xuan1788 发表于 2020-7-24 10:39:59

"""
Find the sum of all the primes smaller than 2 million
"""
import math
from math import sqrt, floor
import time
from time import time
def primeList(n):
i = 7
pL =
gap = 2
while i < n:
   f = 1
   for j in range(2, floor(sqrt(i))+1):
         if i%j == 0:
            f = 0
            break
   if f:
         print(i)
         pL.append(i)
   gap = 6 -gap
   i += gap
return pL

if __name__ == '__main__':
N = 2000000
start = time()
print(sum(primeList(N)))
end = time()
print('costing: %.3f' % (end-start))

583164028 发表于 2020-8-10 10:14:44

99592938 发表于 2017-3-14 18:00
卧槽，跑下来都4分多钟了
答案：>>>
142913828922

超时了欧拉所有习题要求1分钟内出结果

有马_冬巳 发表于 2020-10-4 17:45:02

'''10 以下的质数的和是 2 + 3 + 5 + 7 = 17。
找出两百万以下所有质数的和。'''

def sum_of_prime(unnum):
sum = 0
if unnum >= 2:
   sum += 2
for number in range(3,unnum+1, +2):
         check = 0
         for prime in range(3,int(math.sqrt(number))+1):
            if number % prime == 0:
               check += 1
               break
         if check == 0:
            sum += number
print("%d以下质数的和为: %d" %(unnum,sum))

start_unnum = time.time()
sum_of_prime(2000000)
time_unnum = time.time() - start_unnum
print("%f秒" %time_unnum)

2000000以下质数的和为: 142913828922
10.314830秒

gonorth 发表于 2020-11-5 16:03:57

import math as m
import datetime

def is_prime(n):
if n > 1:
   if n == 2:
         return True
   if n % 2 == 0:
         return False
   for each in range(3, int(m.sqrt(n)) + 1):
         if n % each == 0:
            return False
   return True
return False

def get_prime(n):
while 1:
   if is_prime(n):
         yield n
   n = n + 1

def solve():
start = datetime.datetime.now()

total = 0
for i in get_prime(2):
   if i < 2000000:
         total = total + i
   else:
         print(total)
         end = datetime.datetime.now()
         print(end - start)
         return
solve()

永恒的蓝色梦想 发表于 2021-1-12 18:47:43

jerryxjr1220 发表于 2016-10-10 19:23
最快的求质数的方法：
142913828922

埃氏筛,没欧拉筛快

永恒的蓝色梦想 发表于 2021-2-20 13:21:33

翅膀团发表于 2015-7-21 12:25
你的机子int的范围我不知道，但我的机子的int是4字节，即-2147483648 ~ +2147483647 。2百万还是装得下的

答案的范围可不只2e6

a1351468657 发表于 2021-3-6 18:35:09

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

main()
{
int i, j, flag = 1, num = 2000000;
int begin, end; //记录运行时间
begin = time(NULL);

long long int sum = 0;
while (num > 1)
{
j = sqrt(num + 1);
for (i = 2; i < j; i++)
{
if (num % i == 0)
{
flag = 0;
}
if (flag == 0)
{
goto Label;
}
}
if (flag == 1)
{
sum += num;
}

Label:flag = 1;
num--;
}

end = time(NULL);
printf("time=%d\n", end - begin);

printf("两百万以内素数和为：%lld\n", sum);

}

time=1
两百万以内素数和为：143042032122

改进了两次然后时间控制在1s，望大佬指点！

页: 1 2 [3] 4

鱼C论坛's Archiver