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

ruharley

我使用的是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 秒。

幻世伽蓝

#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;
}

改了好久，终于出来了

BngThea

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)

#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

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=[2]
n=3
while n<=2000000:
        if prime(n):
                p.append(n)
        n+=2
print('2百万以内有%d个质数，它们的和是%d' %(len(p),sum(p)))

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

山有扶苏啊

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

愿你

#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);
}

王小召

运行结果：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())

永恒的蓝色梦想

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[0] = is_prime[1] = 0;


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

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

            if (k >= UPPER_BOUND) {
                break;
            }

            is_prime[k] = false;

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


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

1666194196

#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

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

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))

有理由相信

t = int(input('不就是找素数嘛！输入范围直接开始吧'))
num = [2]
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[i] == 0:
        continue
    for k in num:
        if k > i**0.5:
            break
        elif i % k == 0:
            n[i] = 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[l*i**k] = 0
            k = k + 1
print("所有素数和为")
print(str(a))

这是我以前编的，我觉得效率挺高

代号-K

void calculatePrimeSum(ElementType value, ElementType *answer)
{
    ElementType array[100000] = {0};
    *answer = 2;
    array[0] = 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[k] == 0)
                {
                    yes = false;
                    break;
                }
                k++;
            }
            // join answer
            if(yes)
            {
                *answer += j;
                array[i++] = j;
            }
        }
        j += 2;
        yes = true;
    }
}

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

xuan1788

"""
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 = [2, 3, 5]
    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

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

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

有马_冬巳

'''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

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()

永恒的蓝色梦想

jerryxjr1220 发表于 2016-10-10 19:23
最快的求质数的方法：
142913828922
[Finished in 1.8s]

埃氏筛,没欧拉筛快

永恒的蓝色梦想

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

答案的范围可不只2e6

a1351468657

#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，望大佬指点！