鱼C论坛

 找回密码
 立即注册
楼主: 欧拉计划

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

[复制链接]
发表于 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 秒。



想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-7-1 20:34:01 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <math.h>

  3. int zs(int n)
  4. {
  5.     int i;
  6.     for(i=2;i<=(int)sqrt(n);i++)
  7.     {
  8.         if(n%i==0)
  9.             return 0;
  10.     }
  11.     return n;
  12. }

  13. int main()
  14. {
  15.     long long sum = 2;
  16.     int i = 3;
  17.     for(;i<2000000;)
  18.     {
  19.         if(zs(i))
  20.         {
  21.             sum += i;
  22.         }
  23.         i+=2;
  24.     }
  25.     printf("%lld",sum);
  26.     return 0;
  27. }
复制代码


改了好久,终于出来了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

发表于 2017-9-12 13:58:50 | 显示全部楼层
  1. total = 0
  2. for n in range(2, int(2e6)):
  3.     for i in range(2,n//2+1):
  4.         if not n % i:
  5.             n = 0
  6.             break
  7.     total += n

  8. print(total)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

匿名鱼油  发表于 2018-3-7 22:35:41
本帖最后由 永恒的蓝色梦想 于 2020-6-20 11:48 编辑
  1. #include<stdio.h>
  2. #include<math.h>
  3. int main()
  4. {
  5.         int i,j,tag=1;
  6.         double sum=0;
  7.         for(i=2;i<2000000;i++)
  8.         {
  9.                 for(j=2;j<=sqrt(i);j++)
  10.                 {
  11.                         if(0==i%j)
  12.                         {
  13.                                 tag=0;
  14.                                 break;
  15.                         }
  16.                 }
  17.                 if(1==tag)
  18.                 {
  19.                         sum=sum+i;
  20.                 }
  21.                 tag=1;
  22.         }
  23.         printf("%.0lf\n",sum);
  24.     return 0;
  25. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具

发表于 2018-4-15 11:35:11 | 显示全部楼层
  1. import math

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

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


输出结果是
2百万以内有148933个质数,它们的和是142913828922
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-10-15 09:14:32 | 显示全部楼层
  1. from math import sqrt
  2.    
  3. def is_prime(x):
  4.     if x==1:
  5.         return False
  6.     for i in range(2, int(sqrt(x)) + 1):
  7.         if x%i == 0:
  8.             return False
  9.     return True

  10. s = 0
  11. for t in range(1, 2000000):
  12.     if is_prime(t):
  13.         s = s+t
  14. print(s)
复制代码



142913828922
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-3-15 20:11:46 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <math.h>
  3. int isprime(int x)
  4. {
  5.         long long int i;
  6.         for(i=2;i<=sqrt(x);i++)
  7.         {
  8.                 if(x%i==0)
  9.                 {
  10.                         return 0;
  11.                 }
  12.         }
  13.         return 1;

  14. }
  15. main()
  16. {
  17.         long long i,sum;
  18.         sum=0;
  19.         for(i=2;i<2000000;i++)
  20.         {
  21.                 if(isprime(i))
  22.                         sum=sum+i;
  23.         }
  24.         printf("%lld",sum);
  25. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-10 15:00:20 | 显示全部楼层
运行结果:142913828922
运行时间:12.464479899999999(速度很慢,算法需要优化)
  1. import math
  2. import time


  3. def isprime(num):
  4.     num_s = int(math.sqrt(num))
  5.     for i in range(2, num_s + 1):
  6.         if num % i == 0:
  7.             return 0
  8.             break
  9.     return num


  10. def get_sum(max):
  11.     sum = 0
  12.     for x in range(2, max):
  13.         sum += isprime(x)
  14.     return sum

  15. print(get_sum(2000000))
  16. print(time.process_time())
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-8-3 20:29:32 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2021-2-20 20:47 编辑

C++ 11ms
  1. #include<iostream>
  2. #include<vector>
  3. #include<array>



  4. int main() {
  5.     using namespace std;
  6.     ios::sync_with_stdio(false);

  7.     constexpr unsigned int UPPER_BOUND = 2000000;
  8.     static array<bool, UPPER_BOUND> is_prime;
  9.     vector<unsigned int> primes;
  10.     unsigned long long result = 0;
  11.     unsigned int i, k;
  12.     is_prime.fill(true);
  13.     is_prime[0] = is_prime[1] = 0;


  14.     for (i = 2; i < UPPER_BOUND; i++) {
  15.         if (is_prime[i]) {
  16.             primes.push_back(i);
  17.             result += i;
  18.         }

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

  21.             if (k >= UPPER_BOUND) {
  22.                 break;
  23.             }

  24.             is_prime[k] = false;

  25.             if (!(i % j)) {
  26.                 break;
  27.             }
  28.         }
  29.     }


  30.     cout << result << endl;
  31.     return 0;
  32. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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);
       
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-11-5 21:01:47 | 显示全部楼层
实在想不出好办法,只能用蠢办法了。。看来得先去把数学课好好再上上。。


  1. list1 = []
  2. for i in range(2, 2000000) :
  3.         flag = 0
  4.         for j in range(2, int(i ** 0.5) + 1) :
  5.                 if i % j == 0 :
  6.                         flag += 1
  7.         if flag < 1 :
  8.                 list1.append(i)
  9.                 print(i)
  10. print(sum(list1))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-10 19:53:32 | 显示全部楼层
  1. t = int(input('不就是找素数嘛!输入范围直接开始吧'))
  2. num = [2]
  3. n = []
  4. a = 0
  5. while a <= t:
  6.     n.append (a)
  7.     a = a + 1
  8. a = 2
  9. i = 2
  10. while i <= t - 1:
  11.     f = 1
  12.     i = i + 1
  13.     if n[i] == 0:
  14.         continue
  15.     for k in num:
  16.         if k > i**0.5:
  17.             break
  18.         elif i % k == 0:
  19.             n[i] = 0
  20.             f = 0
  21.             break
  22.     if f == 1:
  23.         num.append (i)
  24.         a = a + i
  25.         k = 1
  26.         while k <= i**i:
  27.             if i**k > t:
  28.                 break
  29.             for l in num:
  30.                 if l*i**k > t:
  31.                     break
  32.                 n[l*i**k] = 0
  33.             k = k + 1
  34. print("所有素数和为")
  35. print(str(a))
复制代码

这是我以前编的,我觉得效率挺高
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-12 19:34:58 | 显示全部楼层
  1. void calculatePrimeSum(ElementType value, ElementType *answer)
  2. {
  3.     ElementType array[100000] = {0};
  4.     *answer = 2;
  5.     array[0] = 2;
  6.     int i = 1;
  7.     int j = 3;
  8.     int k = 0;
  9.     bool yes = true;
  10.     while(true)
  11.     {
  12.         if(j > value)
  13.         {
  14.             break;
  15.         }
  16.         else
  17.         {
  18.             k = 0;
  19.             while( k < i)
  20.             {
  21.                 if(j % array[k] == 0)
  22.                 {
  23.                     yes = false;
  24.                     break;
  25.                 }
  26.                 k++;
  27.             }
  28.             // join answer
  29.             if(yes)
  30.             {
  31.                 *answer += j;
  32.                 array[i++] = j;
  33.             }
  34.         }
  35.         j += 2;
  36.         yes = true;
  37.     }
  38. }

  39. int main(int argc, char *argv[])
  40. {
  41.     ElementType  ret;
  42.     calculatePrimeSum(200000, &ret);
  43.     printf("%lld\n", ret);
  44.     return 0;
  45. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-7-24 10:39:59 | 显示全部楼层
  1. """
  2. Find the sum of all the primes smaller than 2 million
  3. """
  4. import math
  5. from math import sqrt, floor
  6. import time
  7. from time import time
  8. def primeList(n):
  9.     i = 7
  10.     pL = [2, 3, 5]
  11.     gap = 2
  12.     while i < n:
  13.         f = 1
  14.         for j in range(2, floor(sqrt(i))+1):
  15.             if i%j == 0:
  16.                 f = 0
  17.                 break
  18.         if f:
  19.             print(i)
  20.             pL.append(i)
  21.         gap = 6 -gap
  22.         i += gap
  23.     return pL

  24. if __name__ == '__main__':
  25.     N = 2000000
  26.     start = time()
  27.     print(sum(primeList(N)))
  28.     end = time()
  29.     print('costing: %.3f' % (end-start))
复制代码


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-10 10:14:44 | 显示全部楼层
99592938 发表于 2017-3-14 18:00
卧槽,跑下来都4分多钟了
答案:>>>
142913828922

超时了  欧拉所有习题  要求1分钟内出结果
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-4 17:45:02 | 显示全部楼层
  1. '''10 以下的质数的和是 2 + 3 + 5 + 7 = 17。
  2. 找出两百万以下所有质数的和。'''

  3. def sum_of_prime(unnum):
  4.     sum = 0
  5.     if unnum >= 2:
  6.         sum += 2
  7.     for number in range(3,unnum+1, +2):
  8.             check = 0
  9.             for prime in range(3,int(math.sqrt(number))+1):
  10.                 if number % prime == 0:
  11.                     check += 1
  12.                     break
  13.             if check == 0:
  14.                 sum += number
  15.     print("%d以下质数的和为: %d" %(unnum,sum))

  16. start_unnum = time.time()
  17. sum_of_prime(2000000)
  18. time_unnum = time.time() - start_unnum
  19. print("%f秒" %time_unnum)
复制代码



2000000以下质数的和为: 142913828922
10.314830秒
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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()
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-1-12 18:47:43 From FishC Mobile | 显示全部楼层
jerryxjr1220 发表于 2016-10-10 19:23
最快的求质数的方法:
142913828922
[Finished in 1.8s]

埃氏筛,没欧拉筛快
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-2-20 13:21:33 From FishC Mobile | 显示全部楼层
翅膀团 发表于 2015-7-21 12:25
你的机子int的范围我不知道,但我的机子的int是4字节,即-2147483648 ~ +2147483647 。2百万还是装得下的

答案的范围可不只2e6
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-3-6 18:35:09 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <time.h>

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

  9.         long long int sum = 0;
  10.         while (num > 1)
  11.         {
  12.                 j = sqrt(num + 1);
  13.                 for (i = 2; i < j; i++)
  14.                 {
  15.                         if (num % i == 0)
  16.                         {
  17.                                 flag = 0;
  18.                         }
  19.                         if (flag == 0)
  20.                         {
  21.                                 goto Label;
  22.                         }
  23.                 }
  24.                 if (flag == 1)
  25.                 {
  26.                         sum += num;
  27.                 }
  28.        
  29.         Label:flag = 1;
  30.                 num--;
  31.         }

  32.         end = time(NULL);
  33.         printf("time=%d\n", end - begin);
  34.        
  35.         printf("两百万以内素数和为:%lld\n", sum);

  36. }
复制代码

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

改进了两次然后时间控制在1s,望大佬指点!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 09:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表