The Sum of Prime Numbers below 2 million

[CMinus]

Hello all , I am solving Project Euler Puzzles and now I have a little problem with problem 10 which asks me to Sum the Prime Numbers below 2 millions
It's link :
http://projecteuler.net/problem=10

My code works perfectly below small amounts (tested below 200k)
But below 2 Millions It consumes a lot a lot of time
It has been 11 Minutes for now and I have no Result yet
So I ask is there another way to make it more efficient and faster !!

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

int main () 
{
	int num=1;
	long int total=0;
	int divisor;
	
	bool prime = true ;
	
	while (num<2000000)
	{
prime=true;
	if (num<=1)
		prime=false;
	else if(num==2||num==3)
		prime=true;
	else if (num%2==0)
	prime = false ;
	else
	{
		
		for(divisor=3; divisor <num;divisor+=2)
		{
		if (num%divisor==0){
		prime=false;
		break;
		}
		
		}
		
	}
if (prime==true){
	total=total+num;
	
	
}

		num+=2;}
	cout<<"Their Sum is " << total+2;
	
	system("PAUSE");
}

and I think it will take days to sum them !! So Any Suggestions ??

[sedative16]

Here, this worked for me:

#include <iostream>
using namespace std;
int main () {
    long int i,j,s=6,x,nr;
    bool v=true;
    cout <<"nr=";
    cin >>nr;
    for (i=4;i<=nr;i++) {
        v=true;
        for (j=2;j<i;j++) {
            x=i%j;
            if (x==0) v=false;
            }
        if (v==true) s+=i;
        }
        cout <<"the sum is: "<<s<<endl;
        system("pause");
        return 0;
    }

What I did there actually was: knowing that 1,2,3 are prime numbers, i excluded them but I initialized the sum "s" with 6. then I checked every number if they divide with any number from 2 to the actual number minus 1, so if they do not, they are prime and I sum them, if not, I dont sum them. Hope it helps you! Cheers!

[tntxtnt]

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
   //PROTOTYPES
   bool isPrime(int num);

   //LOCAL DECLARATIONS
   long long sum = 2;  //start with sum include 2, the only even prime number
                                 
   //PROCEDURES
   for (int i = 3; i < 2000000; i += 2)    //skip even number
   {
      if (isPrime(i))
      {
         sum += i;
         //cout << " " << i << " ";
      }
   }

   cout << sum << endl;
   return 0;
}

//---------------------------------------------------------
// FUNCTION DEFINITIONS
//---------------------------------------------------------
bool isPrime(int num)
{
   if (num < 2) 
      return false;
   if (num == 2)   //only let one even number pass
      return true;
   if (!(num % 2))  //other even numbers: return false
      return false;
   //You just check for a few numbers, until i > sqrt of num
   //Ex: for 100 use just need to check ODD NUMBER less than sqrt(100) = 10
   //that is 3,5,7,9  not 100 numbers
   for (int i = 3; i <= sqrt((double)num); i += 2) 
      if (!(num % i))
         return false;
   return true;
}

About 4-5s run time for this code...

You see sqrt of 2 millions is 1414, so the fastest way is you only need to check if num is divided by all the prime numbers less than 1414.
Run the code first to get all the primes less than 1414 and write the result to a file, then in the next run you open the file and read all the primes to an array, then write a new isPrime() function to check for only those prime...

[cire]

Sedative, you're using the same algorithm as CMinus except yours is less efficient, because you don't skip testing even numbers.

A couple things. long isn't going to cut it; you're using a signed type, which effectively halves the range of numbers it can hold.

One thing you could do to improve the speed is keep track of the primes you've already found. Then instead of looping through and moduloing every odd number, you can just test against the primes you've already found, but I doubt that will be speed it up enough to be terribly practical.

google for ways to generate prime numbers.

[georgep]

Remember, you needn't check for factors above the number's root as you are simply repeating what you have already done.

This doesn't really matter for small numbers (as you have said) but take 2,000,000 for example. The square root of 2,000,000 is ~1414. If you check all the numbers up to 1414, that's 1414 calculations. However, if you check all the numbers up to 2,000,000 that's clearly 2,000,000 calcualtions. This is why your program is taking a long time.

This is a simple function that you can use to determine whether a number is prime:

bool prime(int n){
 int a = 1;
   while(a <= sqrt(n)){
      a += 1;
      if(n % a == 0){
         return false;
      }
   }
 return true;
}

Note that this uses the sqrt() function, and so requires the <cmath> header.

[JLBorges]

Oh! For heaven's sake, for fast generation of prime numbers use a sieve algorithm. In most cases one wouldn't need anything more than the simplest sieve, one that has been known to mankind for some 2500 years now.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The naivest possible implementation

// generate all prime numbers <= n
std::vector<int> generate_primes( int n )
{
    std::vector<bool>sieve( n, true ) ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] )
          for( auto j = i*i ; j < sieve.size() ; j += i ) sieve[j] = false ;

    std::vector<int> primes ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i )
        if( sieve[i] ) primes.push_back(i) ;
    return primes ;
}

would be faster than any algorithm that needs to test for divisibility.

[CMinus]

Thanks all after modifying my code and Putting the Upper limit to the divisor to be 1414
It comes easily and I put A little more piece of code because the if condition will make the prime false if
It the number is the same as divisor : Here is the code after Modifying :)

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

int main () 
{
	int num=1;
	unsigned long long int total=2;
	int divisor;
	
	bool prime = true ;
	
	while (num<2000000)
	{
prime=true;
	if (num<=1)
		prime=false;
	else if(num==2||num==3)
		prime=true;
	else if (num%2==0)
	prime = false ;
	else
	{
		
		for(divisor=3; divisor <1415;divisor=divisor+2)
		{
			if (num==divisor)
				prime=true; 
		else if (num%divisor==0){
		prime=false;
		break;
		}
		
		}
		
	}
if (prime==true){
	total=total+num;
	
	
}

		num=num+2;
	}
	cout<<"Their Sum is " << total;
	
	system("PAUSE");
}

ah Last Note I initialized Total = 2 because my code skips Even Numbers :)