Program that Finds the first 250000 Prime Numbers

[mpark4656]

Program Specification:
1. Must store the primes in long long type array
2. Must display each prime number
3. Must be the first 250000 primes


I've posted a similar thread before and I've optimized this code (I don't know how to make this any faster at this point).

On my system, this program completes in 23 seconds. I am curious how fast this program will execute on different computers.

IF this program completes under 10 seconds on your computer (Given that it's possible), please let me know your computer specs and I'd really appreciate it.

And by the way, the 250000th prime number is 3,497,861 so make sure that number is displayed as the last number when the program completes.

Thank you all very much!

/************************************************************************
| Description: This program will identify the first 250000 Prime Numbers|
| and store them in a long long type array                              |
************************************************************************/


#define SIZE 250000
#include <iostream>
#include <cmath>

int main ()
{
    long long first125000Primes [ SIZE ];    // Array to store the first 125000 Prime Numbers. First element is 2
    bool isPrime;
    int iter = 1;                            // Used to control while loop & as index for first125000Primes array
    int squareRoot;

    long long currentNumber = 3;             // First number to be tested and it will be incremented by 2

    first125000Primes [ 0 ] = 2;             // First element is always 2, which is the first prime number

    std::cerr << first125000Primes [ 0 ] << std::endl; // Display the first element in the array

    while ( iter < SIZE ) {
        isPrime = true;     // Reset boolean var to true

        squareRoot = std::sqrt ( currentNumber );   // Find the square root of the current number being tested

        // Go through the list of all previously found primes and divide the sqrt of the current number by each element
        // As soon as the number is divisible, flag it as "Not Prime" and break the loop
        for ( int index = 0 ; first125000Primes [ index ] <= squareRoot; index ++ )
            if ( currentNumber % first125000Primes [ index ] == 0 ) {
                isPrime = false;
                break;
            }

        // If the number is prime, store the value in the next index of array and increment iter
        if ( isPrime ) {
            first125000Primes [ iter ] = currentNumber;

            std::cerr << first125000Primes [ iter ] << std::endl;

            iter ++;
        }

        currentNumber += 2;     // Add 2 to currentNumber since it only needs to test odd numbers
    }

    return 0;
}

[integralfx]

Printing out primes to console

Time elapsed: 21.32960 seconds.

Not printing out primes to console

Time elapsed: 0.53605 seconds.

Build options

mingw32-g++.exe -Wall -fexceptions -march=corei7-avx -O3 -std=c++11

Specs

- i7 4770k (not overclocked at the moment because summer)
- 8GB 1600MHz RAM

I added a timer in the source.

// first line after int main()
auto start = chrono::high_resolution_clock::now();

/*
variable declarations, calculating primes, etc.
*/

// after while(iter < SIZE) loop
auto finish = chrono::high_resolution_clock::now();
auto elapsed = chrono::duration_cast<chrono::duration<double>>(finish - start);
cout << "\nTime elapsed: " << fixed << setprecision(5) << elapsed.count() << " seconds.\n";

[JLBorges]

#include <iostream>
#include <cmath>
#include <cassert>
#include <limits>
#include <vector>
#include <ctime>

int main()
{
    const auto start = std::clock() ;
    constexpr std::size_t NPRIMES = 1'000'000 ; // *** one million, 250'000 is a bit too low to time accurately.
    static long long primes[NPRIMES] {} ;

    // use the prime number theorem to get an upper bound on the nth prime
    // https://en.wikipedia.org/wiki/Prime_number_theorem
    const auto logn = std::log(NPRIMES) ;
    const auto sz = NPRIMES * ( logn + std::log(logn) ) + 1 ;
    assert( sz < std::numeric_limits<std::size_t>::max() ) ;

    // generate a prime number sieve upto the upper_bound
    std::vector<bool> sieve( sz, true ) ;
    const std::size_t rp1 = std::sqrt(sz) + 2 ;
    for( std::size_t i = 2 ; i < rp1 ; ++i ) if( sieve[i] )
        for( std::size_t j = i+i ; j < sz ; j += i ) sieve[j] = false ;

    // set the numbers in the array to prime numbers till the nth prime number
    std::size_t cnt = 0 ;
    for( std::size_t i = 2 ; i < sz && cnt <= NPRIMES ; ++i ) if( sieve[i] ) primes[cnt++] = i ;

    const auto end = std::clock() ;
    std::cout << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;

    // a few sanity checks
    assert( cnt == NPRIMES+1 && primes[0] == 2 ) ;
    if( NPRIMES >= 250'000 ) assert( primes[ 250'000 - 1 ] == 3'497'861 ) ; // and by the way, the 250000th prime number is 3,497,861
    if( NPRIMES >= 1'000'000 ) assert( primes[ 1'000'000 - 1 ] == 15'485'863 ) ; // http://primes.utm.edu/lists/small/millions/

    std::cout << "\nthe " << NPRIMES << "th prime number is " << primes[NPRIMES-1] << '\n' ;

    std::cout << "\ndisplay each prime number. Must be the first 250000 primes:\n"
                 "surely you are joking, aren't you?\n" ;
}

180 milliseconds

the 1000000th prime number is 15485863

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

[integralfx]

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_and_variants

#include <iostream>
#include <chrono>
#include <iomanip>
#include <cmath>
using namespace std;

int main()
{
	/* TIMER START */
	auto start = chrono::high_resolution_clock::now();
	/* TIMER START */

	const int limit{ (int)1e6 };

	bool primesArr[limit];
	for (int i{ 0 }; i < limit; i++){
		primesArr[i] = true;
	}
	primesArr[0] = false; primesArr[1] = false;

	/* Algorithm for finding primes */
	/* Sieve_of_Eratosthenes --> "https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_and_variants" */
	for (int i{ 2 }; i < (int)sqrt(limit); i++)
	{
		if (primesArr[i])
		{
			for (int j{ i*i }; j < limit; j+=i){
				primesArr[j] = false;
			}
		}
	}

	/* Print out prime numbers */
	/*
	for (int i{ 0 }; i < limit; i++)
	{
		if (primesArr[i]){
			cout << i << endl;
		}
	}
	*/

	/* TIMER FINISH */
	auto finish = chrono::high_resolution_clock::now();
	auto elapsed = chrono::duration_cast<chrono::duration<double>>(finish - start);
	cout << "\nTime elapsed: " << fixed << setprecision(5) << elapsed.count() * 1000 << " ms.\n";
	/* TIMER FINISH */

	cout << "\nPress enter to continue . . .\n";
	cin.get();
}

// when printing out primes
Time elapsed: 6447.21400 ms.

// when not printing out primes
Time elapsed: 3.00300 ms.

[mpark4656]

Thank you all for the input. I apologize it took me a while to respond. I was occupied with other stuff. I understand the problem now.

I will play around with Sieve of Erastosthenes more.