c++ - 低于2000000的素数总和？

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

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

我的代码:

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

最佳答案

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

为了检查给定的整数是素数，您需要检查它的除数不小于或等于其平方根。因为，如果除数大于平方根，则商将为整数，并且小于平方根。

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