Question About my Prime Function

[mpark4656]

This is a short/simple program I wrote for a bigger project down the road.

Program Purpose: To store 125000 prime numbers in an long long type array.

If you examine my codes, you will notice that it is programmed to store the first 200 prime numbers, NOT 125000. Eventually, the program will have to store 125000 Prime Numbers. But for the time being and for testing/debugging purpose, I will use 200.

Standard Output line (cout) was included in this program to check to make sure the program is working as intended, but once this is converted to a class member function, that COUT line will go away.

I tried to run this program with 125000 index and it took OVER 5 minutes to get all 125000 prime numbers to standard output. I am afraid that it will take that much long to run the program once this program is converted to a class member function.

I am wondering if there is a way to improve the efficiency of this program before I use it for my project.



Algorithm I used in this program:
Starting with 2 (2 is the very first prime number), check to see if it is divisible by any number higher than 1 but lower than the number itself

For example, if number 2 is tested, it will simply be marked as a prime.
If number 3 is tested, the program will attempt to divide 3 by 2 and if it is not divisible, number 3 will be marked as a prime.
If number 10 is tested, the program will attempt to divide 10 by 2, 3, 4, 5, 6, 7, 8, 9 and if any of these can divide 10, then 10 will be marked as a non-prime.



Here is the Code.

Again, any assistance will be greatly appreciated.

Thank you all in advance!

/************************************************************************
| Description: This program will identify the first 125000 Prime Numbers|
| and store them in an array                                            |
************************************************************************/


#include <iostream>

int main ()
{
    long long first125000Primes [200];           // Array to store the first 125000 Prime Numbers

    int i = 0;                                   // Used to control while loop

    long long currentNumber = 2;

    while ( i < 200 )
    {
        bool isPrime = true;

        for ( int l = 2; l < currentNumber; l ++ )
        {
            if ( currentNumber % l == 0 )
            {
                isPrime = false;
            }
        }

        if ( isPrime )
        {
            first125000Primes[i] = currentNumber;

            std::cout << first125000Primes[i] << std::endl;     // Send to standard output to verify that the array stores prime numbers

            i ++;                                               // Increment if the number is a prime
        }

        currentNumber ++;
    }

    return 0;
}

[JayhawkZombie]

Consider using https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

A brute force algorithm will grow exponentially in computation time. You probably notice already that even computing the first 200 takes a while (comparatively, it's still fast).

[mpark4656]

Haha... just as soon as you posted the first comment, JayhawkZombie, I noticed something myself.

My program was testing ALL numbers between 1 and the number itself. It means that 7000 will have to test against like 6998 numbers and it does increase the computation time as the number gets larger.

I just revised my code. Basically, as soon as the number is divisible, the loop will stop and test the next number. This is MUCH faster now. I will read the Wikipedia article and try to understand it.

Here is my revised code!

/************************************************************************
| Description: This program will identify the first 125000 Prime Numbers|
| and store them in an array                                            |
************************************************************************/


#include <iostream>

int main ()
{
    const int INDEX = 200;

    long long first125000Primes [INDEX];           // Array to store the first 125000 Prime Numbers

    int i = 0;                                   // Used to control while loop

    long long currentNumber = 2;

    while ( i < INDEX )
    {
        bool isPrime = true;

        for ( int l = 2; l < currentNumber && isPrime; l ++ )
        {
            if ( currentNumber % l == 0 )
            {
                isPrime = false;
            }
        }

        if ( isPrime )
        {
            first125000Primes[i] = currentNumber;

            std::cout << first125000Primes[i] << std::endl;     // Send to standard output to verify that the array stores prime numbers

            i ++;                                               // Increment if the number is a prime
        }

        currentNumber ++;
    }

    return 0;
}

[JayhawkZombie]

Even that is a MUCH better improvement. With the sieve, you only test up to the square root of the nth prime you're trying to find (100th prime would test up to 10).

I have an implementation of this if at some time you'd like to see it. I also have an implementation in Haskell, but let's not talk about that.

[48T7M4Gy]

I am wondering if there is a way to improve the efficiency of this program before I use it for my project.

This is a very time consuming way of working out primes.

If you use the Sieve of Eratosthenes algorithm the calculations are completed in a matter of seconds on a reasonable PC. The 125000th prime is 1655131 so your method will be a mountain of divisions.

[dhayden]

Some other simple changes to your code:
- At line 23, only test up to sqrt(currentNumber), but be sure to compute this value into a variable first, and then use the variable in the loop. You don't want to compute sqrt each time through the loop.
- Also, rather than dividing by all numbers, just divide by the primes that you've already found.

With these changes, my computer finds the first 125,000 primes in about 0.5 seconds.

[mpark4656]

I am still trying to implement Sieve of Eratosthenes algorithm.

In the mean time, I changed my codes to divide the number by the primes that I've already found and it is much faster.

@dhayden
I tried to implement sqrt ( currentNumber ) but I think I may be doing something wrong since it causes the program to be slower than the original. Dividing by the primes I've already found helped a lot though. Can you show me an example?

@kemort
You're right. It is a lot of divisions. I will try to implement Sieve of Eratosthenes algorithm

@JayhawkZombie
If you can show me the implementation of Sieve of Eratosthenes later, I'd appreciate it. But right now, I want to try to implement it by myself first.

This is the code that I have so far right now and with my PC, it can find all 125000 primes in 90 seconds (70 Seconds without std::cout statement). Once I get back home, I will start implementing Sieve of Eratosthenes.

/************************************************************************
| Description: This program will identify the first 125000 Prime Numbers|
| and store them in an array                                            |
************************************************************************/

#include <iostream>
#include <cmath>

int main ()
{
    const int INDEX = 125000;

    long long first125000Primes [INDEX];           // Array to store the first 125000 Prime Numbers

    int i = 0;                                   // Used to control while loop

    long long currentNumber = 2;

    while ( i < INDEX )
    {
        bool isPrime = true;

        for ( int l = 0; l < i && isPrime; l ++ )
        {
            if ( currentNumber % first125000Primes[l] == 0 )
            {
                isPrime = false;
            }
        }

        if ( isPrime )
        {
            first125000Primes[i] = currentNumber;

            std::cout << first125000Primes[i] << std::endl;     // Send to standard output to verify that the array stores prime numbers

            i ++;                                               // Increment if the number is a prime
        }

        currentNumber ++;
    }

    return 0;
}

[48T7M4Gy]

http://www.sanfoundry.com/cpp-program-implement-sieve-eratosthenes/
This implementation of the Sieve is worth considering :)

[dhayden]

Can you show me an example?

Here is the code I used:

#include <iostream>
#include <cmath>

int main ()
{
    const int INDEX = 125000;
    long long primes [INDEX];           // Array to store the first 125000 Prime Numbers
    int i = 0;                                   // Used to control while loop
    long long currentNumber = 2;

    while ( i < INDEX ) {
        bool isPrime = true;
        int top = std::sqrt(currentNumber);
        for (int idx = 0; idx < i && primes[idx] <= top; ++idx) {
            if (currentNumber % primes[idx] == 0) {
                isPrime = false;
                break;
            }
        }

        if ( isPrime ) {
            primes[i] = currentNumber;
            std::cout << primes[i] << std::endl;
            i ++;
        }
        currentNumber ++;
    }

    return 0;
}

[mpark4656]

@dhayden

Thank You! I see what you meant in the earlier post now.
I will try your method and see if I can reduce the computation time.

@kemort
That link is blocked on the computer that I am on right now. I will check it out later



I've been working on designing / planning Sieve of Eratosthenes but I am unable to compile and test the code yet, but this is the design that I have so far. Can you tell me whether I am on the right track?

/***************************************************************************
Description: This program will identify the first 125000 Prime Numbers and store them in an array
***************************************************************************/



//* int main ()
//* {
//**	An Integer: 1655131 because it is the 125000th Prime number
//**
//**	bool first125000Primes [1655131]
//**
//**	Initialize the array to "true"
//**
//**	sqrtInteger = std::sqrt ( integer );
//**
//**	for ( int i = 2; i <= sqrtInteger; i ++ )
//***		if first125000Primes [ i ] is true
//***			for j = i^2, i^2 + i, i^2 + 2i, i^2 + 3i, ... , not exceeding n
//****				first125000Primes [ j ] = false
//**
//**	Output: all i such that first125000Primes [ i ] is true
//* }

//-----------------------------------------------------------------------------------------------------------------------

//* int main ()
//* {
//**	int integer = 1655131;
//**
//**	bool first125000Primes [1655131];
//**
//**	// Initialize the array to "true"
//**	for ( int i = 2; i <= 1655131; i ++ )
//**		first125000Primes [ i ] = true;
//**
//**	int sqrtInteger = std::sqrt ( integer );
//**
//**	int index = 0;
//**
//**	for ( int i = 2; i <= sqrtInteger; i ++ )
//***		if  ( first125000Primes [ i ] == true )
//****			for ( int j = std::pow ( i, 2 ) + i * index ; j <= integer ;  )
//*****				first125000Primes [ j ] = false;
//*****				index ++;
//*****				j = std::pow ( i, 2 ) + i * index
//**
//**	Output: all i such that first125000Primes [ i ] is true			
//* }

//-----------------------------------------------------------------------------------------------------------------------

//* int main ()
//* {
//**	int integer = 1655131;
//**
//**	bool first125000Primes [1655131];
//**
//**	// Initialize the array to "true"
//**	for ( int i = 2; i <= 1655131; i ++ )
//**		first125000Primes [ i ] = true;
//**
//**	int sqrtInteger = std::sqrt ( integer );
//**
//**	int index = 0;
//**
//**	for ( int i = 2; i <= sqrtInteger; i ++ )
//***		if  ( first125000Primes [ i ] == true )
//****			for ( int j = std::pow ( i, 2 ) + i * index ; j <= integer ;  )
//*****				first125000Primes [ j ] = false;
//*****				index ++;
//*****				j = std::pow ( i, 2 ) + i * index
//**
//**	for ( int i = 2; i <= 1655131; i ++ )
//***		if ( first125000Primes [ i ] == true )
//****			std::cout << i << std::endl;
//*
//*	return 0; 			
//* } 

[48T7M4Gy]

Save you the trouble, this is the program:

/*
* C++ Program to implement Sieve of Eratosthenes
*/

#include <iostream>
const int len = 100;

int main()
{
	int arr[100] = { 0 };
	for (int i = 2; i < 100; i++)
	{
		for (int j = i * i; j < 100; j += i)
		{
			arr[j - 1] = 1;
		}
	}

	for (int i = 1; i < 100; i++)
	{
		if (arr[i - 1] == 0)
			std::cout << i << "\t";
	}
}

As for the version I use cout is the time consuming bit. To do the processing only and produce a list of the first 125000 primes takes substantially less than the few seconds I mentioned earlier.

[mpark4656]

@kemort

I tested the implementation of Sieve of Eratosthenes that you posted.

The program is efficient, but it can't be used to calculate 125000 prime numbers, at least not with array.

The 125000th prime number is 1,655,131, which means the index for arr[] has to be 1655131

/*
* C++ Program to implement Sieve of Eratosthenes
*/

#include <iostream>
const int len = 1655131;

int main()
{
	int arr[100] = { 0 };
	for (int i = 2; i < len; i++)
	{
		for (int j = i * i; j < len; j += i)
		{
			arr[j - 1] = 1;
		}
	}

	for (int i = 1; i < len; i++)
	{
		if (arr[i - 1] == 0)
			std::cout << i << "\t";
	}
}

Apparently, 1655131 is too large and the implementation of Sieve of Eratosthenes will not work with array variable, at least not on my system. Maybe I am missing something here?

The purpose is NOT finding all prime numbers up to 125000 but rather the program is supposed to find the first 125000 prime numbers.

[mpark4656]

@dhayden

Your code finds all 125000 primes in 11 seconds on my system, which is much better than what I have right now (90 seconds).

I will study your codes in detail.

However, I still wanna know if there is a way to implement Sieve of Ertosthenes.

[48T7M4Gy]

/*
* C++ Program to implement Sieve of Eratosthenes
*/

#include <iostream>
#include <math.h> // <--

const uint64_t len = 1655131; // <--

int main()
{
	int  arr[len] = { 0 };  // <--
	for (int i = 2; i < sqrt(len); i++) // <--
	{
		for (int j = i * i; j < len; j += i)
		{
			arr[j - 1] = 1;
		}
	}

	for (int i = 1; i < len; i++)
	{
		if (arr[i - 1] == 0)
			std::cout << i << "\t";
	}
}

There's an interesting point with this algorithm related to line 19: for (int j = i * i; j < len; j += i) The same answer is produced if for (int j = i + i; j < len; j += i) which embodies Eratosthenes more closely. Go figure somebody :)