rohanbojja rohanbojja - 2 months ago 14
C++ Question

Sum of prime numbers below 2000000?

How do i find the sum of all primes below 2 million? Project Euler 10th question, http://projecteuler.net/problem=10.
I tested my code for below 10 and works like a charm. But below 2 million does not seem to work :/ It has been about 15 minutes and still going, I don't think it should take that long, Right? I'll try the sum function but I still don't get why this isn't working?

EDIT: I figured I can't use the sum function as the numbers don't even get stored in the array :/

My code:

#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

Your problem is that your program will check for too many unnecessary divisors.

In order to check that a given integer is a prime, you need to check that it has no divisor lesser or equal to its square root. Because, if there was a divisor greater than the square root, the quotient would be an integer, and would be lesser than the square root.

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

You could use a vector instead:

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