6
\$\begingroup\$

There are many problems on the Internet that require you to find prime numbers, so I decided to write a set of functions to find them. I used the Sieve of Eratosthenes for generating the primes as it was fast and easy to implement compared to other algorithms.

However, I'm wondering if my code, rather than my method, is inefficient. Am I using STL containers/iterators correctly? Is there any section in my code slowing down the program?

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define initial_prime_barrier 100
bool isFlagged(int i) { return i == 0; }
bool isNextStart(int i) { return i != 0; }

vector<int> generatePrimesBelow(int limit)
{
   vector<int> primes;
   for (int i = 2; i < limit; i++)
   {
      primes.push_back(i);
   }  
   vector<int>::iterator currentStart = primes.begin();
   do
   {
      int numberAtStart = *currentStart;
      vector<int>::iterator currentNumber = currentStart + numberAtStart;
      do
      {
         *currentNumber = 0;
         advance(currentNumber, numberAtStart);
      } while (currentNumber < primes.end());
      currentStart = find_if(currentStart + 1, primes.end(), isNextStart);
   } while ((*currentStart) * (*currentStart) < limit);
   vector<int>::iterator newEnd = remove_if(primes.begin(), primes.end(), isFlagged);
   primes.erase(newEnd, primes.end());
   return primes;
}

bool isPrime(int number)
{
   static vector<int> primes = generatePrimesBelow(initial_prime_barrier);
   static int numPrimes = primes.size();
   static int largestPrime = primes[numPrimes-1];
   static int halfwayPrime = primes[numPrimes/2];
   if (number == largestPrime)
   {
      return true;
   }
   else if (number < largestPrime)
   {
      if (number == halfwayPrime)
      {
         return true;
      }
      else if (number > halfwayPrime)
      {
         for (int i = numPrimes/2; i < numPrimes; i++)
         {
            if (number == primes[i])
            {
               return true;
            }
         }
      }
      else if (number < halfwayPrime)
      {
         for (int i = numPrimes/2; i >= 0; i--)
         {
            if (number == primes[i])
            {
               return true;
            }
         }
      }
   }
   else if (number > largestPrime)
   {
      primes = generatePrimesBelow(number + number);
      numPrimes = primes.size();
      largestPrime = primes[numPrimes-1];
      halfwayPrime = primes[numPrimes/2];
      return isPrime(number);
   }
   return false;
}

int main (int argc, char * const argv[]) 
{
   const int number = 123123;
   cout << (isPrime(number) ? "YES" : "NO") << endl;
}
\$\endgroup\$
5
\$\begingroup\$

I take it you are really hell bent to use STL for everything but maybe you are over using it. However your code as it is, is very redundant. The specific issue I found are:

  1. Whenever you call isPrime(), you are generating the primes array inside generatePrimesBelow() from scratch. Its not a problem now, but if you call isPrime() from main inside a loop for a couple of numbers, it will be very inefficient.
  2. Since you are using only one vector<int> for storing both the primes and the sieve, you are using find_if(), remove_if() and erase() which would not be needed if you use 2 vectors for storing the primes and the sieve separately, and hence make the code more efficient.
  3. In isPrime(), you can simply use the find() function from STL to look whether your number is in primes or not. You don't need to write your own look-up code. Better yet, since the primes is sorted, you can directly use binary_search() STL algorithm on it. But all of this is moot as should search for a number to be prime or not if you have already found whether it is prime or not using generatePrimesBelow().

As per my understanding you can do everything in your isPrime() function itself, including what you are doing in generatePrimesBelow() in lesser lines of code that what your current isPrime() looks like. Here is what you can do:

  1. Have two vectors<int>, primes and eratosthSieve with eratosthSieve's size being the number - 1 where number was passed in as argument.
  2. Use STL generate algorithm to populate eratosthSieve from 2 to number, by having a function passed in as the generating function. It would like like this:

    int fillUp() {
        static int i = 1;
        return ++i;
    }
    

    and will be used as generate( eratosthSieve.begin(), eratosthSieve.end(), fillUp)

  3. Your sieve logic would become something like this with the two vectors:

    vector<int>::iterator currentStart = eratosthSieve.begin();
    vector<int>::iterator currentNumber;
    do 
    {
        int numberAtStart = *currentStart;
        if ( numberAtStart != 0 )                 // If the number is 0, it means has been filtered out in the sieve.
        {
            primes.push_back( numberAtStart);
            currentNumber = currentStart + numberAtStart;
            do
            {
                *currentNumber = 0;
                advance(currentNumber, numberAtStart);
            } while (currentNumber < eratosthSieve.end());        
        }
        currentStart = find_if(currentStart + 1, eratosthSieve.end(), isNextStart);
    } while (currentNumber < eratosthSieve.end());
    
  4. Check if the last element of the primes vector is equal to number or not: return ( number == primes.back() );

\$\endgroup\$
  • \$\begingroup\$ So would there be 2 loops? One to filter the sieve and another to get the primes from it? \$\endgroup\$ – rcplusplus Feb 23 '12 at 15:33
  • \$\begingroup\$ Yeah. You were already using 2 loops in your generatePrimesBelow(). I've used the almost same code. \$\endgroup\$ – vvnraman Feb 23 '12 at 22:57
3
\$\begingroup\$

You could use std::set. Then you do not need to recreate the list of prime numbers every time you break the limits (only add missing numbers).

Also, the search for the existence of element is easier.

So, with using set, your function would be at least 10 times shorter, therefore easier to understand and maintain.

\$\endgroup\$
  • \$\begingroup\$ Would that affect speed in any way? \$\endgroup\$ – rcplusplus Feb 23 '12 at 15:42
  • \$\begingroup\$ @rcplusplus standard library's algorithms are optimized, therefore I would say "yes, it would most likely improve speed.". \$\endgroup\$ – BЈовић Feb 23 '12 at 16:06
2
\$\begingroup\$

Some additional things not mentioned in the other answers:

  • Try not to use using namespace std.

  • You could order your #includes in some way (such as alphabetically) for better organization.

  • #define is not commonly used in C++ for constants, unlike in C, for various reasons.

    Use const for these instead:

    const int initial_prime_barrier = 100;
    
  • At a glance, isFlagged() and isNextStart() may look like function prototypes (single line and at the top), which they are not. I'd recommend having the definition on separate lines, like with the other functions.

    bool isFlagged(int i)
    {
        return i == 0;
    }
    

    bool isNextStart(int i)
    {
        return i != 0;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.