c++ - 2000000 以下的质数之和？

Question

我如何找到小于 200 万的所有素数的总和？欧拉计划第十题，http://projecteuler.net/problem=10 .我测试了我的代码低于 10 并且工作得很好。但是低于 200 万似乎不起作用:/已经大约 15 分钟了，而且还在继续，我认为不应该花那么长时间，对吗？我将尝试 sum 函数，但我仍然不明白为什么它不起作用？

编辑:我想我不能使用 sum 函数，因为数字甚至没有存储在数组中:/

我的代码:

#include <iostream>

using namespace std;

int main()
{
    unsigned long long x,y,z=0,s[200000],a,sum=0;
    bool isprime;
    for(x=3;x<2000000;x++)
    {
        for(y=2;y<x;y++)
        {
            if(x%y!=0 && x!=y)
            {
                isprime =true;
            }
            else
            {
                isprime =false;
                break;
            }
        }
        if(isprime ==true)
        {
                s[z] = x;
                z++;
                isprime = false;
        }
    }
    cout<<z;
    for(a=0;a<z;a++)
    {
        sum=sum+s[a];
        cout<<"Sum is being calculated "<<sum<<"\n";
    }
    cout<<"The sum is "<<sum+2<<" LADIES";
}

Answer 1

你的问题是你的程序会检查太多不必要的除数。

为了检查给定整数是否为素数，您需要检查它是否没有小于或等于其平方根的除数。因为，如果有一个大于平方根的除数，商就是一个整数，并且小于平方根。

#include <iostream>

using namespace std;

int main()
{
    unsigned long long x,y,z=0,s[200000],a,sum=0;
    bool isprime;
    for(x=3;x<2000000;x++)
    {
        for(y=2; y*y <= x ;y++)
        {
            if(x%y!=0 && x!=y)
            {
                isprime =true;
            }
            else
            {
                isprime =false;
                break;
            }
        }
        if(isprime ==true)
        {
                s[z] = x;
                z++;
                isprime = false;
        }
    }
    cout<<z;
    for(a=0;a<z;a++)
    {
        sum=sum+s[a];
        cout<<"Sum is being calculated "<<sum<<"\n";
    }
    cout<<"The sum is "<<sum+2<<" LADIES";

您可以改用 vector :

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    unsigned long long x,y;
    std::vector<unsigned long long> primes;
    bool isprime = true;

    for(x=3; x<2000000; x++)
    {
        isprime = true;
        for(y=2; y*y <= x ;y++)
        {
            if(x%y==0 || x==y)
            {
                isprime=false;
                break;
            }
        }
        if(isprime)
        {
            primes.push_back(x);
        }
    }
    unsigned long long sum = 2 + std::accumulate(v.begin(), v.end());
    cout<<"The sum is "<<sum<<" LADIES";
}