find sum of prime numbers till 2 Million..

clmlbx

clmlbx

Technomancer
Problem:-

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


Find the sum of all the primes below two million.

Code: 
#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

harshilsharma63

DIY FTW!
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'.
 
S

sarthak

In the zone
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'.
Click to expand...

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

harshilsharma63

DIY FTW!
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.
Click to expand...
> Sorry, my mistake.

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

clmlbx

Technomancer
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.
Click to expand...

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

142913828922

This way I solved 10th problem from Project Euler.. :-D
 
S

sarthak

In the zone
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::-(

I need solution fasten this programme

Answer is below in spoiler tags if any one is wondering

142913828922

This way I solved 10th problem from Project Euler.. :-D
Click to expand...

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

Desmond

Destroy Erase Improve
Staff member
Admin
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.
 
S

sarthak

In the zone
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.
Click to expand...

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

nightcrawler

Broken In
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.
Click to expand...

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

harshilsharma63

DIY FTW!
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::-(

I need solution fasten this programme

Answer is below in spoiler tags if any one is wondering

142913828922

This way I solved 10th problem from Project Euler.. :-D
Click to expand...
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

rijinpk1

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

ico

Super Moderator
Staff member
Takes about < 3 seconds on my PC.

PHP: 
#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

harshilsharma63

DIY FTW!
@ico
When I ran your code:

PHP: 
#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.
 
Last edited:
ico

ico

Super Moderator
Staff member
^^ dunno, the answer is fine at my place.

*i.imgur.com/V2dLf4e.png
 
dashing.sujay

dashing.sujay

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

*i.imgur.com/ofZ0hb5.png
 
OP
clmlbx

clmlbx

Technomancer
Code: 
#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

*i43.tinypic.com/2zjmb13.png


@ico your code output is 1179908154

*i43.tinypic.com/r9g1lu.png

my processing time is more because of my old system.. C2D 1.8 ghz....I Guess
 
Last edited:
ico

ico

Super Moderator
Staff member
Use a 64-bit compiler. :)

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

clmlbx

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

ico

Super Moderator
Staff member
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

vickybat

I am the night...I am...
PHP: 
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).
 
You must log in or register to reply here.
Top Bottom