n Prime Numbers..

[arjunvmm004]

Write a c++ program to print out the first n prime numbers and the sum of the first n prime numbers.

[eyenrique]

Hi @arjunvmm004,
can you post
what you have
so far? (code)

[JLBorges]

#include <iostream>
#include <cmath>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
   std::size_t n = 1000000 ; // number of primes to be summed up
   // std::cin >> n ; // n * ( logn + std::log(logn) ) < max value size_t can hold

   // use the prime number theorem to get an upper bound on the nth prime
   // http://en.wikipedia.org/wiki/Prime_number_theorem
   const auto logn = std::log(n) ;
   const std::size_t SZ = n * ( logn + std::log(logn) ) + 1 ;

   // generate a prime number sieve upto the upper_bound
   // http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
   std::vector<bool> sieve( SZ, true ) ;
   const std::size_t ub_root = std::sqrt(SZ) + 2 ;
   for( std::size_t i = 2 ; i < ub_root ; ++i ) if( sieve[i] )
       for( std::size_t j = i+i ; j < SZ ; j += i ) sieve[j] = false ;

   // count and sum up till the nth prime number
   std::size_t cnt = 0 ;
   boost::multiprecision::cpp_int sum = 0 ;

   for( std::size_t i = 2 ; i < SZ && cnt < n ; ++i ) if( sieve[i] )
   {
      ++cnt ;
      sum += i ;
      // printing out of i elided
   }

   std::cout << "sum of the first " << n << " prime numbers: " << sum << '\n' ;
}

http://coliru.stacked-crooked.com/a/b56d7c4223c2417c

[abhishekm71]

@JLBorges

Please can you explain this part:

const std::size_t ub_root = std::sqrt(SZ) + 2 ;
   for( std::size_t i = 2 ; i < ub_root ; ++i ) if( sieve[i] )
       for( std::size_t j = i+i ; j < SZ ; j += i ) sieve[j] = false ;

EDIT:
Shouldn't it be:

const std::size_t ub_root = std::sqrt(SZ) + 2 ;
   for( std::size_t i = 2 ; i < ub_root ; ++i ) if( sieve[i] )
       for( std::size_t j = 2*i ; j < SZ ; j += i ) sieve[j] = false ;

Thanks

[JLBorges]

i+i == 2*i

[giblit]

actually it should be i*i The values before then will already be removed. Although I also do my sieve slightly different instead of removing all the evens (the most to remove) I just have my vector contain the odds only.This way you can increment by 2 * i instead of i to make it faster.


Here is an example of what I mean by the i * i

There are probably neater ways then the bit shift but I found it easiest this way to sq them.

//Inital
    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

//removal of 2's
    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

//removal of 3's notice how the 6 is already cross out
//so we can start at 9 (increment of 6)
    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

//removal of 5's now(we can safely skip all evens after 2s are gone)
//the first 5 will be at 25 since
//5 is prime , 10 is removed by 2 , 15 is removed by 3, 20 is removed by2
    2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

It may not be as neat as JLBorges but here is how I do my sieves:

#include <iostream>
#include <vector>
#include <cmath>

int main()
{
    //primes less than 1 million not the first 1 million
    const unsigned max = 1e6; //1 million
    const unsigned sqrt = std::sqrt( max );
    
    std::vector<bool> primes( max/2 , true ); //supposedly you can fit 8 bool into 1 byte if its in a vector
    //though if its less than 8 it will still be 1 byte
    //container will store 3->1e6+1
    
    for( unsigned i = 3; i < sqrt; i += 2 )//odds only //index 0 = 3 , index 1 = 5 , index 2 = 7, ect...
    //some cases you may want <= sqrt also if say the sqrt is 7.3 it will round down to 7 but you will want to check for 7s.
    {
        if( primes.at((i>>1)-1) )//if current index is a prime
        {
            for( unsigned j = ((i * i) >>1) - 1; j <= max/2; j += i )//incremting by 2 * i really since I removed all evens already
            {
                primes.at(j) = false; //could use an if statement so you don't replace
                //ones that are already set but may slow down speed
            }
        }
    }
    
    unsigned sum = 2; //2 is prime
    unsigned count = 1;
    for( unsigned i = 0; i < primes.size(); ++i )
    {
        if( primes.at( i ) )
        {
            sum += i * 2 + 3;
            ++count;
        }
    }
    
    std::cout << "The sum of primes below 1 million are: " << sum << std::endl;
    std::cout << "With a total of: " << count << " primes" << std::endl;
}

http://coliru.stacked-crooked.com/a/25faa43ef58cdffd

*fixed a typo.

though I think somewhere I messed something up I'm very tired.

*edit just realized I was missing an if statement when i was getting the sum.

[JLBorges]

> actually it should be i*i

giblit +1


> Although I also do my sieve slightly different instead of removing all the evens
> (the most to remove) I just have my vector contain the odds only.
> This way you can increment by 2 * i instead of i to make it faster.

Sieve of Sundaram http://en.wikipedia.org/wiki/Sieve_of_Sundaram

[abhishekm71]

@JLBorges
Sorry I thought it was i + 1 :)