rohanbojja - 1 year ago 98
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";
}
``````

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";
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download