rohanbojja - 9 months ago 53

C++ Question

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

Source (Stackoverflow)