# find sum of prime numbers till 2 Million..



## clmlbx (Apr 29, 2013)

Problem:-

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.


Find the sum of all the primes below two million.


```
#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int flag = 1;
    unsigned long long sum=0,i,j,numb;
    cout << "Enter number untill you Want to find sum of primes : " ;
    cin >> numb;
    for(i=2;i<=numb;i++){
        for(j=2;j<=ceil(i/2);j++){
            if((i%j) == 0){
                flag = 0;
                break;
            }


        }


    if(flag == 1){
        sum += i;
        }else{
        flag = 1;
        }
    }
    cout<<endl<<endl<<"Sum of prime Numbers till "<<numb<<" is "<<sum<<endl<<endl;
    return 0;
}
```

Now again as my previous post,. Logic is correct it even works for 10,20,2000,20000 but as soon as I enter 2 million it some what crashes.. I thought I need bigger data type so used unsigned long but still not working


----------



## harshilsharma63 (Apr 29, 2013)

replacing i<=numb with i<=(numb/2) will decrease the number if iterations without affecting the result. For a number 'n', and number >(n/2) cannot be a perfect divisor of 'n'.


----------



## sarthak (Apr 29, 2013)

harshilsharma63 said:


> replacing i<=numb with i<=(numb/2) will decrease the number if iterations without affecting the result. For a number 'n', and number >(n/2) cannot be a perfect divisor of 'n'.



numb is the number upto which we have to check for primes, not the number to be checked for prime. So if you take numb/2 it will check for only half as many numbers.

@OP whats in the variable ceil ? I can't find its declaration.


----------



## harshilsharma63 (Apr 29, 2013)

sarthak said:


> numb is the number upto which we have to check for primes, not the number to be checked for prime. So if you take numb/2 it will check for only half as many numbers.
> 
> @OP whats in the variable ceil ? I can't find its declaration.


> Sorry, my mistake.

> Ceil is not a variable, its a function. Ceil(x.y) returns x.0 + 1;


----------



## clmlbx (Apr 30, 2013)

sarthak said:


> numb is the number upto which we have to check for primes, not the number to be checked for prime. So if you take numb/2 it will check for only half as many numbers.
> 
> @OP whats in the variable ceil ? I can't find its declaration.



ceil just rounds the number to its upper side.. so 4.6 will be 5

Ok Guys I found out the Hard way code is right.. but it took 9425.266 seconds to find out. .. that is too slow: 

I need solution fasten this programme

Answer is below in spoiler tags if any one is wondering



Spoiler



142913828922



This way I solved 10th problem from Project Euler..


----------



## sarthak (Apr 30, 2013)

clmlbx said:


> ceil just rounds the number to its upper side.. so 4.6 will be 5
> 
> Ok Guys I found out the Hard way code is right.. but it took 9425.266 seconds to find out. .. that is too slow:
> 
> ...



Start the outer for loop from i=3 and increment by 2. So it would check for only odd numbers and not the even ones which are not prime.

Also try googling for efficient algorithms to generate prime numbers.


----------



## Desmond (Apr 30, 2013)

Why are you using a flag variable? Why not simply put an else statement after the "if" where you check the mod of i and j is zero and add the sum there? It is not much but I think it should make is somewhat faster.


----------



## sarthak (May 1, 2013)

DeSmOnD dAvId said:


> Why are you using a flag variable? Why not simply put an else statement after the "if" where you check the mod of i and j is zero and add the sum there? It is not much but I think it should make is somewhat faster.



Dude.............OP is generating prime numbers, for which the number must not be divided by any other number. If he places an else there then it would not only consider many composites as primes but also add them up multiple times.


----------



## nightcrawler (May 1, 2013)

sarthak said:


> Start the outer for loop from i=3 and increment by 2. So it would check for only odd numbers and not the even ones which are not prime.
> 
> Also try googling for efficient algorithms to generate prime numbers.



Agree to this one. Also if what I think instead of looking for Ceil(i/2) you should look at sqrt(i). Will give you even lesser iterations.

Hope this helps


----------



## harshilsharma63 (May 4, 2013)

clmlbx said:


> ceil just rounds the number to its upper side.. so 4.6 will be 5
> 
> Ok Guys I found out the Hard way code is right.. but it took 9425.266 seconds to find out. .. that is too slow:
> 
> ...


Actually you didnt. If it took more than a minute, it's inappropriate. try to use multiple threads or a better algorithm for prime check.


----------



## rijinpk1 (May 4, 2013)

In the second loop
j<=sqrt(i)
is more than enough and that reduces number of iterations. Try and tell.


----------



## ico (May 4, 2013)

Takes about < 3 seconds on my PC.


```
#include <stdio.h>
#include <math.h>
#define LIMIT 2000000

int isPrime(unsigned long int);

int main()
        {
        unsigned long int i,sum=0;
        for(i=2;i<LIMIT;i++)
                if(isPrime(i))
                        sum += i;
        printf("Sum = %ld\n",sum);
        return 0;
        }

int isPrime(unsigned long int n)
        {
        unsigned long int i,flag=0;
        for(i=2;i<=sqrt(n);i++)
                {
                if(n%i==0)
                        {
                        flag=1;
                        break;
                        }
                }
        if(flag)
                return 0;
        else
                return 1;
        }
```
*Output:*
Sum = 142913828922


----------



## harshilsharma63 (May 4, 2013)

@ico
When I ran your code:


```
#include <stdio.h>
#include <iostream>
#define LIMIT 2000000
int isPrime(unsigned long int);
int main()
{        
unsigned long int i,sum=0;        
for(i=2;i<LIMIT;i++)               
 if(isPrime(i))                       
 sum += i;        
printf("Sum = %ld\n",sum);        
return 0;        
}
int isPrime(unsigned long int n)        
{        
unsigned long int i,flag=0;        
for(i=2;i<=sqrt(n);i++)                
{                
if(n%i==0)                       
 {                        
flag=1;                        
break;                        
}                
}        
if(flag)                
return 0;       
 else                
return 1;        
}
```

the output comes to be 1179908154.


----------



## ico (May 4, 2013)

^^ dunno, the answer is fine at my place.

*i.imgur.com/V2dLf4e.png


----------



## dashing.sujay (May 5, 2013)

^Even my system is giving 1179908154 as answer with execution time ~5 secs. Checked with GCC & VS:2010.



Spoiler



*i.imgur.com/ofZ0hb5.png


----------



## clmlbx (May 5, 2013)

```
#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int flag = 1;
    unsigned long long sum=0,i,j,numb;
    cout << "Enter number untill you Want to find sum of primes : " ;
    cin >> numb;
    for(i=3;i<=numb;i+=2){
        for(j=2;j<=sqrt(i);j++){
            if((i%j) == 0){
                flag = 0;
                break;
            }


        }


    if(flag == 1){
        sum += i;
        }else{
        flag = 1;
        }
    }
    cout<<endl<<endl<<"Sum of prime Numbers till "<<numb<<" is "<<sum+2<<endl<<endl;
    return 0;
}
```


After the changes as discussed here It completed in 28 seconds



Spoiler



*i43.tinypic.com/2zjmb13.png




@ico your code output is 1179908154



Spoiler



*i43.tinypic.com/r9g1lu.png



my processing time is more because of my old system.. C2D 1.8 ghz....I Guess


----------



## ico (May 5, 2013)

Use a 64-bit compiler. 


```
[gagan@cozmo3 ~]$ gcc lol.c -m32 -lm
[gagan@cozmo3 ~]$ ./a.out 
Sum = 1179908154
```


----------



## clmlbx (May 5, 2013)

I am using code blocks with  GCC compiler (mingw). any recommendation for 64 bit compiler for windows.


----------



## ico (May 5, 2013)

May be minigw-w64?

By default Microsoft VC++ compiles to 32-bit. You can configure it to compile to 64-bit. Data type ranges can vary from architecture to architecture and OS to OS.

Best is to use Linux itself for all C programming. You can also use OpenMP with gcc for parallel programming.


----------



## vickybat (May 5, 2013)

```
bool isPrime(unsigned long int n)
        {
        unsigned long int i,count=0;
        for(i=1;i<=n;i++)
                {
                if(n%i==0)
                        {
                        count++;
                        
                        }
                }
        if(count == 2)
                return True;
        else
                return False;
        }
```

Isn't this version of prime checker more better than the ones described above? I mean a prime number is divisible by one and itself i.e two times.
So testing that case will give us if a number is prime or not ( count value is 2).


----------



## harshilsharma63 (May 5, 2013)

vickybat said:


> ```
> bool isPrime(unsigned long int n)
> {
> unsigned long int i,count=0;
> ...


It is valid, but not optimized. the function definition provided by ico is highly optimized. By optimized, I mean that the number of iterations to check the primitivity are extremely low in ico's code. Suppose one needs to test 20000000 for being prime number, then for loop in your code will be executed 2000000 times.


----------



## vickybat (May 5, 2013)

harshilsharma63 said:


> It is valid, but not optimized. the function definition provided by ico is highly optimized. By optimized, I mean that the number of iterations to check the primitivity are extremely low in ico's code. Suppose one needs to test 20000000 for being prime number, then for loop in your code will be executed 2000000 times.



Ok....how about now??


```
bool isPrime(unsigned long int n)
        {
        unsigned long int i,count=0;
        for(i=2;i<=sqrt(n);i++)
                {
                if(n%i==0)
                        {
                        count++;
                        
                        }
                }
        if(count == 1)
                return True;
        else
                return False;
        }
```


----------



## ico (May 5, 2013)

^^ break out of the loop when n%i==0 condition is met the first time. If you won't, you'll still have sqrt(n) iterations.


----------



## vickybat (May 5, 2013)

ico said:


> ^^ break out of the loop when n%i==0 condition is met the first time. If you won't, you'll still have sqrt(n) iterations.



Yeah but i still can't understand the logic in your code mate. Lets say, the number is 18. Now at i = 2, the condition n%i ==0 is satisfied and flag is set to 1 and breaks out of loop.
Lets say for 17, it breaks only at sqrt(17). Every time, it will return 0 as flag will always be 1.

Now how does your code decide 17 is a prime number and 18 is not? Am i missing something here buddy?

Maybe my head has gone nuts cracking a solution for sudoku in python.


----------



## ico (May 5, 2013)

vickybat said:


> Yeah but i still can't understand the logic in your code mate. Lets say, the number is 18. Now at i = 2, the condition n%i ==0 is satisfied and flag is set to 1 and breaks out of loop.
> Lets say for 17, it breaks only at sqrt(17). Every time, it will return 0 as flag will always be 1.


No, flag won't be 1 in my code for 17. It will remain 0 itself. For 17, for every number from 2 to sqrt(17), the if condition won't get satisfied. For 18, 18%2 will result in 0. If condition gets satisfied, flag value is set and the loop breaks off.

Your code infact will not result in the right answer for 18 and even 19. There's no need of "counting" actually. 


```
bool isPrime(unsigned long int n)
        {
        unsigned long int i,count=0;
        for(i=2;i<=sqrt(n);i++)
                {
                if(n%i==0)
                        {
                        count++;
                        
                        }
                }
        if(count == 1)
                return True;
        else
                return False;
        }
```

*i.imgur.com/TtuBXOU.png


----------



## rijinpk1 (May 5, 2013)

Flag=1=> not prime
flag=0=>prime


----------



## vickybat (May 5, 2013)

ico said:


> *No, flag won't be 1 in my code for 17. It will remain 0 itself. For 17, for every number from 2 to sqrt(17), the if condition won't get satisfied.* For 18, 18%2 will result in 0. If condition gets satisfied, flag value is set and the loop breaks off.
> 
> Your code infact will not result in the right answer for 18 and even 19. There's no need of "counting" actually.



Silly me, yes, *num/sqrt(num) != 0 *  but *num/sqrt(num)=sqrt(num)*  and hence it won't work. My code will work only if iterated through N and then counted (My earlier code).

Yes, i got the flag concept now. Its far more efficient. Man the sudoku problem had my brain all screwed up. 

*@ico*

That was really silly from my side. Sorry for bothering mate.


----------



## clmlbx (May 6, 2013)

Hello guys I think my last solution is most optimized one ..difference between ico and mine is that mine just checks for odd numbers and not even numbers so. many less iteration..

I just am not much clear about sqrt(n) I have used.. as I First used ceil(i/2).. that is easy for example

Number is 50 -> ceil(50/2)->25 so only check till that else it wont be ever divisible by a number greater then 25.

But how does sqrt works.. say number is 16 -> sqrt(16)-> 4  but still it is divisible with 8.. 

so kindly please some one explain that.. I am not a maths student..


----------



## rijinpk1 (May 6, 2013)

For 50 , it is still not required to run upto 25. Upto Sqrt (50)=7 is more than enough. So for huge numbers, you are saving a lot of executions and hence less complexity and faster execution


----------



## vickybat (May 6, 2013)

clmlbx said:


> But how does sqrt works.. say number is 16 -> sqrt(16)-> 4  but still it is divisible with 8..
> 
> so kindly please some one explain that.. I am not a maths student..



Let me explain this mate. In ico's code, the for statement is something like this:


```
for ( i =2;i<=sqrt(n);i++)
```

So the number of iterations will be from 2 to sqrt(n).

Now ico's code checks for divisibility. If true, then the number is not prime and if false, the number is prime.

For 16, it will be divided by 2 and will yield 0 as remainder in the first iteration. Hence the flag variable is set and loop breaks proving the number is not prime.
For 17, it won't yield 0 if divided by 2 upto sqrt(17) because even for the last iteration, *17/sqrt(17) == sqrt(17) and not 0*. So the condition *( if n%i == 0)* is never satisfied and the flag isn't set, thus returning 1, i.e number is prime.

I hope i am clear.


----------



## nims11 (May 6, 2013)

To be frank, all the approaches in this thread are really bad for the question. Let me Give a step by step tutorial on prime numbers that atleast everyone should know.

*1. Noob method*

```
#include<iostream>
using namespace std;
bool isPrime(int n)
{
    if(n == 1)
        return false;
    if(n == 2)
        return true;
    for(int i=2;i<n;i++)
        if(n%2 == 0)
        return false;
    return true;
}
int main()
{
    int sum = 0;
    int limit = 2000000;
    for(int i=2;i<=limit;i++)
    {
        if(isPrime(i))
            sum += i;
    }
    cout<<sum<<endl;
}
```
No need to explain this.
Actual Time Taken : Don't have that much patience!
Time complexity: O(n^2) (Really Bad!)

*2. Some obvious improvements*


```
#include<iostream>
using namespace std;
bool isPrime(int n)
{
    if(n == 1)
        return false;
    if(n == 2)
        return true;
    if(n%2 == 0)
        return false;
    for(int i=3;i<n/2;i+=2)
        if(n%i == 0)
        return false;
    return true;
}
int main()
{
    int sum = 2;
    int limit = 2000000;
    for(int i=3;i<=limit;i+=2)
    {
        if(isPrime(i))
            sum += i;
    }
    cout<<sum<<endl;
}
```
Checking Only odd numbers for divisibility with odd numbers. (Note: I have maintained the universality of the isPrime())
In words, If a number is divisible by 2, it is simply not prime unless it is 2 itself. Moreover, if it is not divisible by 2, it is not divisible by any multiple of 2 (2*x) as well.
Also, if it is not divisible by 2, it won't be divisible by any number > n/2 as well (I will generalize this in the next step).

Actual Time Taken : Don't have that much patience!
Time complexity: Still O(n^2) with slightly lesser constant (Really Bad!)

*3. Some real Improvement*

```
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
    if(n == 1)
        return false;
    if(n == 2)
        return true;
    int lt = n;
    for(int i=2;i<=lt;i++, lt=n/i)
        if(n%i == 0)
        return false;
    return true;
}
int main()
{
    int sum = 2;
    int limit = 2000000;
    for(int i=3;i<=limit;i+=2)
    {
        if(isPrime(i))
            sum += i;
    }
    cout<<sum<<endl;
}
```

Notice that isPrime() first assumes that the number is prime, then tries to find a case where it is contradicted. Thus, it will run till it finds a divisor for *n*. In the last point, I made an optimization that if *n* is not divisible by 2, we can reduce the upper bound to *n/2*. Why not do the same for other numbers as well. If in isPrime(), if the loop is at say, i=x and it doesn't divide *n*, then we can say that *n* is not divisible by any number 2,3,4,5....,x. Thus, we can safely reduce the upper bound to *n/x*. This drastically reduces the Time requirements.

Actual Time Taken : 1.478s
Time complexity: O(n*sqrt(n)) (Not Bad!)

*4. Improvising the previous approach*

The previous isPrime() can be written as

```
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
    if(n == 1)
        return false;
    if(n == 2)
        return true;
    int lt = sqrt(n);
    for(int i=2;i<=lt;i++)
        if(n%i == 0)
        return false;
    return true;
}
```

In last point, as *i* increases by 1, *lt* decreases to *lt/i*. So where does they meet? *i<=n/i  => i*i<=n  => i<=sqrt(n)*.

Actual Time Taken : 0.780s
Time complexity: O(n*sqrt(n)) with reduced constant (Not Bad!)

*5. Real Stuff*
0.780s is not bad, right?
Wrong! It is a really BAD solution for such questions. It is fine if we had to check some numbers for primality, but for generating primes, this algo is bad for the given limits.
We can exploit one thing in the isPrime() for such prime generation problems. One question, if you checked a number for divisibility by 3, why do you need to check for multiples of 3? i.e, generalize the following optimization we did - _If a number is not divisible by 2, we need not check for its divisibility by even numbers (2*x)_
The generalization is, Only check divisibility by prime numbers. We can implement this by making sure that, while checking for *x* for prime, we already know all previous discovered primes and if *x* is found to be prime, we store it for future use.


```
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector<int> primes;
bool isPrime(int n)
{
  if(n==1)
  return 0;
  int limit=sqrt(n);
  for(int i=0;i<primes.size() && primes[i]<=limit;i++)
      if(n%primes[i]==0)
        return false;
  return true;
}
void generatePrimes(int n)
{
  primes.push_back(2);
  for(int i=3;i<=n;i+=2)
  {
    if(isPrime(i))
    {primes.push_back(i);}
  }
}
int main()
{
    int limit = 2000000;
    int sum = 0;
    generatePrimes(limit);
    for(int i=0;i<primes.size();i++)
        sum += primes[i];
    cout<<sum<<endl;
}
```

Actual Time Taken : 0.370s
Time complexity: O(n*P(sqrt(n))) with really less constant, P(x) = number of primes less than x (GREAT! since in worst case P(sqrt(2*10^6)) = 223)

*6. Even Better*
Half of times, the above method works for me. I prefer above method because I derived it myself  but there is a more popular and simpler method called sieve of Sieve of Eratosthenes.
I won't explain this as I am getting bored. But it is really simple to understand. Sieve of Eratosthenes - Wikipedia, the free encyclopedia


```
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int sieve[2000001];
void generatePrimes()
{
    for(int i=2;i<2000001;i++)
    {
        if(!sieve[i])
        {
            if(1LL*i*i<2000001LL)
            for(int j=i*i;j<2000001;j+=i)
                sieve[j] = 1;
        }
    }
}
int main()
{
    int sum = 0;
    generatePrimes();
    for(int i=2;i<2000001;i++)
        if(!sieve[i])
            sum += i;
    cout<<sum<<endl;
}
```


Actual Time Taken : 0.081s
Time complexity: O(n*loglogn) (Excellent!)


----------



## ico (May 7, 2013)

Sieve of Eratosthenes is the best one. There is Sieve of Atkin which is even better. I left it out on purpose for these guys to explore. Using OpenMP parallel for for the inner loop for SoE will result in some more execution time improvement. OpenMP can only be used with loops you aren't breaking out of/returning from within.


----------



## vickybat (May 7, 2013)

Well honestly i had no idea about Sieve of Eratosthenes or Atkins.Thanks to *nims11* and *ico* for mentioning these. Much appreciated guys.


----------



## Gen.Libeb (Jun 17, 2013)

You guys still doing this?
Just started with a noob method & will get to better approaches. Couldn't find any online calculator to verify my results

If you guys have already done this , needed to make sure this is right ?
0 to 10000000  - > 3203324994354


----------



## truegenius (Jun 28, 2013)

```
while(n<=lim)
{for (flag=0,i=2;i<=sqrt(n);i++)
{if (n%i==0)
{flag=1;
break;}}
if (flag==0)
sum+=n;n+=2;}
```

it took 77 seconds for lim=1crore on phenom 2 x6 1090t @4ghz , compiled using borland c++ 4.5
and answer was 3574358836


----------

