Prime number calculator

[Kanoisa]

Hi all,

I have begun workin on getting c++ to do physics and things for me so im working on some maths functions. starting small and working up, Just did this one on prime number generation and was wondering if anyone can point out any ways it could be ,made significantly faster (excluding platform dependant optomisation) or if they can see any technical problems or coding good practise issues. I have checked the output and i think it is solid but i was wondering what you guys here thought.

So heres the code

//primes.cpp prime number calculator 
#include <vector>
#include <limits.h>
#include <iostream>

const unsigned long c_intLimit = 1000;

using namespace std;

int main(int argc, char** argv)
{
    //init vars
    unsigned long result = 0;
    typedef vector<unsigned long> primeList_t;
    primeList_t primes;
    bool isPrime;
    
    //init primes 
    primes.push_back(3);
    primes.push_back(4);

    //for each number 
    for( unsigned long x = 4; x < c_intLimit ; x++ )
    {
        isPrime = true; //assume the number is prime 

        //divide by each prime 
        for( primeList_t::iterator iPrime = primes.begin(); iPrime != primes.end(); iPrime++ )
        {
            result = ( x % (*iPrime) ); //check the result of the division by each prime number
            if( result == 0 )//if the number dives evenly then it is not prime
            {
                isPrime = false;
                break;
            }
            else{}

        }

        //if the number was prime keep it
        if( isPrime )  
        {
            primes.push_back(x);   
        }
    }

    //list generated so print the results
    cout<<"List of prime numbers from 1 -> "<<c_intLimit<<endl;

    for( primeList_t::iterator iPrime = primes.begin(); iPrime != primes.end(); iPrime++ )
    {
        cout<<*iPrime<<endl;
    }
    cout<<"\nEnd of list"<<endl;

    cin.get(); /* i know this is soo wrong and bad but im just lazy in small test appls to use proper pause code here or to pipe output to a file */

	return 0;
}

[jonsca]

cin.get(); /* i know this is soo wrong and bad but im just lazy in small test appls to use proper pause code here or to pipe output to a file */

This is actually one of the most portable and safest methods of pausing.

Just wanted to comment on that, I have no insight into a more effective algorithm.

[Kanoisa]

Is the solution posted here ( http://www.daniweb.com/forums/thread90228.html ) as a tutorial by narue not the best way as it handles more situations consistently? and i dont see that her code would not be portable?

Anyway many thanks for the feedback

[arkoenig]

Since when is 4 prime? Isn't that what you're claiming in line 20 of your code?

Also, if you care about execution time, one easy way to speed things up is to observe that you don't have to divide a candidate by every prime; just by the ones that are <= the square root of the candidate.

You have to be a little bit careful about this to ensure you don't inadvertently treat a perfect square as a prime because of rounding error in the square root, but an easy way to do that is compute the square root, round it, and then increment the rounded square root until its square is greater than the candidate. In other words:

unsigned long limit = sqrt(x);
while (limit * limit < x)
    ++limit;

Now you know that limit is >= sqrt(x) even if there are rounding problems, and you can use iPrime<=limit as the ending condition for your inner loop.

[Kanoisa]

Ahh i see what i done there ,.. i meant to have 2 and 3 there not 3 and 4 ,..good spot.

And if i understand you correctly then this additional exit condition would serve as an alternative break point from the inner loop after my current check?

[jonsca]

Is the solution posted here ( http://www.daniweb.com/forums/thread90228.html ) as a tutorial by narue not the best way as it handles more situations consistently? and i dont see that her code would not be portable?

Anyway many thanks for the feedback

I'm definitely not saying Narue is wrong in that case.

You can certainly flush the stream before you call the cin.get() but a cin.ignore() will get rid of a stray '\n' that could be picked up by your cin.get().

In your code comment, it sounded to me like you wanted to put in a system("pause"); , and that's more what I was trying to dissuade you from.

[Kanoisa]

ooh heck no system("pause"); is the root of all evil imo. Thanks for the response :)

[pseudorandom21]

You could try implementing the sieve of eratosthenes using a vector or a bitset, the wikipedia page on the sieve is decent; the vector is for marking it as not prime.

The indices would be the numbers.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

You also have other options, of course. It is my belief that Era's sieve will be the fastest.
http://en.wikipedia.org/wiki/Sieve_of_Sundaram

Here, this according to wikipedia, is a modern version of Eratosthenes' sieve:
http://en.wikipedia.org/wiki/Sieve_of_Atkin

see also: http://en.wikipedia.org/wiki/Wheel_factorization
And, it's up to you as the master and commander of your project to determine the one that will suit your needs of both difficulty in implementation/time used and the required performance.

[arkoenig]

And if i understand you correctly then this additional exit condition would serve as an alternative break point from the inner loop after my current check?

No, instead of your current check. Once 2 is in the prime vector, the next number to be tested is 3. 2 * 2 is 4, which is strictly greater than 3; so you won't run off the end of the vector even when you're testing 3. Once you've gotten 3 safely onto the prime vector, 5 and subsequent primes are a piece of cake.

So here's one way you might write it:

// This assert should succeed because we pushed 2 onto primes
assert (!primes.empty());

primeList_t::iterator iPrime = primes.begin();
while (*iPrime <= limit && (x % *iprime) != 0) {
    ++iPrime;

    // This assert should work because the square of the last element
    // of primes is strictly greater than x, so the test *iPrime <= limit
    // should ensure that iPrime never referred to the last element of primes
    assert (iPrime != primes.end());

}

if (*iPrime > limit)
    primes.push_back(x);

[Kanoisa]

Thanks again, that makes sense now and i can see how it would greatly improve performance as the prime numbers get bigger.

Ill implement it this way :)

Id say that makes this case closed :)