# Object-oriented design of list of primes

Is there a better way to implement this class, or does it not constitute implementation in the first place? This is one of my first few tries at OOP. Any suggestions will be much appreciated.

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

class PrimeList
{
public:
std::vector<int> vPrime;
void initVector(int n)
{
for (int i=2; i <= n; ++i)
vPrime.push_back(i);
}
};

int main()
{
// Instantiate an object "primes" of type PrimeList.
PrimeList primes;

// Get the input variable to pass to the initVector method.
std::cout << "Enter the upper limit of the list of primes you want     to generate:" << std::endl;
int n;
std::cin >> n;

// Create a vector filled with every integer from 2 to n.
primes.initVector(n);

// Begin the sieve
for (int a=0; a < sqrt(n); ++a) {
for (int b=a+1; b < primes.vPrime.size(); ++b) {
if (primes.vPrime[b] % primes.vPrime[a] == 0) {
primes.vPrime.erase(primes.vPrime.begin() + b);
}
}
}

// Print the list of primes from 2 to n.
for (int i=0; i < primes.vPrime.size(); ++i)
std::cout << primes.vPrime[i] << std::endl;
return 0;
}

• You have a small typo -- sqrt should be std::sqrt. Unfortunately, some compilers don't warn about this, and then we're in for a nasty surprise when the code suddenly refuses to compile on another platform. – Matt Jul 9 '13 at 22:38
• Thanks matt! I think that means this loop was iterating while a < n! Assuming that the compiler just ignored the sqrt() and ran with its parameter. – albertjorlando Jul 9 '13 at 23:15
• @ao2130: not quite. I've been in this same situation before-- my compiler just ignored the absent std:: but still called the function. I have no idea why some compilers don't catch this. – Jamal Jul 9 '13 at 23:22
• What's worse, is that unqualified functions will be called as C-style functions (without overloading -- important, since this means truncation & losing precision). Compare C++'s std::abs (will work on double and others) with C's abs (will only work with int). When a "lenient" (but actually unhelpful) compiler doesn't warn about a misuse like this (which happens all to often :[), the same source code may produce completely wrong results on another platform :-( Really wish compilers (looking at MSVC here in particular) were more strict about this. – Matt Jul 10 '13 at 0:39

• As a general rule for classes: data members (variables), such as vPrime, should be private. They can either be declared under private or outside of public (a class is private by default).

• For a simple use of classes here, you don't need a mutator. Just declare your object with an argument:

PrimeList primes(n);


Since this would make n (or let's just make it number) a data member, modify your constructor as such and initialize the object like this:

// 'n' is the parameter and 'number' is the class's data member
PrimeList::PrimeList(int n) : number(n) {initVector();}


As you can see, the constructor now calls initVector(). With number now as a data member, initVector() no longer needs an argument. Since this function is not part of the interface, make it private.

• The display for-loop in main() can also be put into a class method:

void display() const; // header declaration

// .cpp implementation

void PrimeList::display() const
{
// your object is no longer referenced inside the class
for (int i = 0; i < vPrime.size(); ++i)
{
std::cout << vPrime[i] << std::endl;
}
}


Then simple call it in main() with your object:

primes.display();


Note the use of const fin this function. If you're not changing any data members, create your functions as such. If you accidentally violate this, your compiler will stop you. This is to ensure that your data members are not unintentionally modified, depending on the functions's purpose.

• Your sieve calculations can also be put into a class method. Get the idea now? Again, it should be private. It will NOT be const since you're changing the vector inside the class. You can call it in initVector() since they're both non-const (you cannot call const functions in non-const functions and vice-versa).

• @user2164854: You're welcome! Happy to help. – Jamal Jul 9 '13 at 22:14

Your PrimeList doesn't follow object-oriented design principles; it's just a thin wrapper for a std::vector that doesn't do much.

A goal of object-oriented design is to create objects as "smart" data. Your PrimeList class should know how to maintain itself in a self-consistent state. PrimeList is supposed to know all about how to find prime numbers. Users of the class should be able to ask it what the nth prime number is. Instead, you have made your main() function do all the hard work.

Think about how users of your class would want to call your code. For example, this would be a nice interface:

int main(int argc, char *argv[]) {
PrimeList primes;
// http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_500_prime_numbers
std::cout << primes[0]   << " should be 2"    << std::endl;
std::cout << primes[499] << " should be 3571" << std::endl;
return 0;
}


Now, let's design the class to make that happen. Here's a start:

class PrimeList {
public:
PrimeList();

// Returns the nth prime number
// (primelist[0] is 2, primelist[1] is 3, etc.)
unsigned long operator[](size_t nth);
};


To make that work, though, PrimeList needs to keep some state internally. I would use a vector for running the Sieve of Eratosthenes. For convenience and efficiency, I would keep another vector of just the primes that have been discovered using that sieve. I also need to have some code for creating and maintaining that sieve. That code and the two vectors are part of the internal workings of PrimeList, and are none of the caller's business. Therefore, they should be declared as private members of the PrimeList class:

class PrimeList {
public:
PrimeList();

// Returns the nth prime number
// (primelist[0] is 2, primelist[1] is 3, etc.)
unsigned long operator[](size_t nth);

private:
std::vector<bool> sieve;    // sieve[i] is true if i is prime
std::vector<unsigned long> knownPrimes;

void findMorePrimes();
};


Then, it's just a matter of filling in the code. =) Here is a possible solution.

PrimeList::PrimeList() {
sieve.push_back(false);     // 0 is not prime
sieve.push_back(false);     // 1 is not prime
knownPrimes.push_back(2);
}

unsigned long PrimeList::operator[](size_t nth) {
while (nth >= knownPrimes.size()) {
findMorePrimes();
}
return knownPrimes[nth];
}

void PrimeList::findMorePrimes() {
// Initially, sieve is a vector where every element is assumed
// to be prime (sieve[i] = true).
// Then, we will set sieve[i] = false for all i where i is non-
// prime.  Special cases for non-primes sieve[0] = false and
// sieve[1] = false were already established in the constructor.

// Enlarge the sieve by some arbitrary amount
std::vector<bool>::size_type prevSieveSize = sieve.size();
sieve.resize(4 * prevSieveSize, /* is_prime= */ true);

// Strike out the composite numbers from the enlarged sieve
for (std::vector<unsigned long>::iterator p = knownPrimes.begin();
p != knownPrimes.end();
++p) {
for (std::vector<bool>::size_type multiple = (prevSieveSize / (*p)) * (*p);
multiple < sieve.size();
multiple += (*p)) {
sieve[multiple] = false;
}
}

// Harvest the newly discovered prime numbers
for (std::vector<bool>::size_type i = prevSieveSize; i < sieve.size(); ++i) {
if (sieve[i]) {
knownPrimes.push_back(i);
}
}
}


Note that in order to maintain the illusion of an unbounded list of primes, findMorePrimes() is more complicated than an implementation of the Sieve of a predetermined size. That additional bookkeeping is the price to be paid for the desire to present a pretty interface to the outside world. It's also illustrates the power of object-oriented programming to manage complexity, as you can see in the simplicity of the main() example.

• Properly speaking, PrimeList should use the singleton pattern, but I wanted to keep things simple for now. – 200_success Oct 5 '13 at 7:02