# Find all the primes less or equal than N

This is not a novel interview problem. But I want to address it with the following points:

1. Implement the algorithm with Object-Oriented Design principles in mind.

2. Optimize the solution, if there are many continuous inputs.

3. Write simple unit tests (without using unit testing framework like gtest, boost.test)

Basically, I followed the idea of Sieve of Eratosthenes algorithm. To optimize the solution if there are many continuous inputs, I maintain a vector which stores all the primes we have computed so far. If the new n is smaller than the previous maximal n, we can directly get the primes from "cache" without re-computing the primes again.

I'm specifically looking for suggestions on the algorithm itself, OOD or better unit tests.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class PrimeFinder {
friend class PrimeFinderTest;
public:
PrimeFinder(int n = 2) {
is_prime_.push_back(false);
is_prime_.push_back(false);
is_prime_.push_back(true);
primes_.push_back(2);
n_ = n;
}

vector<int> get_primes(int n) {
if(n <= n_) {
return get_primes_subset(n);
} else {
extend_primes(n);
return primes_;
}
}

private:
vector<bool> is_prime_;
vector<int> primes_;
int n_;

vector<int> get_primes_subset(int n) {
auto iter = primes_.begin();
while(iter != primes_.end()) {
if(*iter <= n) ++iter;
else break;
}
return vector<int>(primes_.begin(), iter);
}

void extend_primes(int n) {
is_prime_.reserve(n + 1);
is_prime_.insert(is_prime_.end(), n - n_, true);

int bound = sqrt(n);
for(int i = 2; i <= bound; ++i) {
if(is_prime_[i]) {
int j = i + i;
while(j <= n) {
if(j > n_) {
is_prime_[j] = false;
}
j += i;
}
}
}

for(int i = n_ + 1; i <= n; ++i) {
if(is_prime_[i]) primes_.push_back(i);
}

n_ = n;
}
};

template <typename T>
string vec2str(const vector<T>& vec) {
string str = "";
for(auto n : vec) {
str += to_string(n) + " ";
}
return str;
}

class PrimeFinderTest {
public:
void test_get_primes_subset(vector<int> origin, int n) {
PrimeFinder test;
test.primes_ = origin;
vector<int> subset = test.get_primes_subset(n);
cout << vec2str(subset) << endl;
}

void test_extend_primes(vector<int> origin, vector<bool> origin_bool, int n) {
PrimeFinder test;
test.primes_ = origin;
test.is_prime_ = origin_bool;
test.n_ = test.is_prime_.size() - 1;
test.extend_primes(n);
assert(test.n_ == n);
assert(test.is_prime_.size() == n + 1);
cout << vec2str(test.primes_) << endl;
}

void test_get_primes(int n) {
PrimeFinder test;
cout << vec2str(test.get_primes(n)) << endl;
}

void test_get_primes_suite(vector<int> nums) {
PrimeFinder test;
for(int num : nums) {
cout << vec2str(test.get_primes(num)) << endl;
}
cout << endl;
}
};

int main() {
PrimeFinderTest test;
test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),7);
test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),8);
test.test_get_primes_subset(vector<int>({2,3,5,7,11,13,17,19}),15);

test.test_extend_primes(vector<int>({2,3,5,7}),
vector<bool>({false, false, true, true, false, true, false, true, false}),
19);

test.test_get_primes(2);
test.test_get_primes(9);
test.test_get_primes(16);
test.test_get_primes(30);

test.test_get_primes_suite(vector<int>({2, 9, 16, 30}));
test.test_get_primes_suite(vector<int>({16, 9, 2, 30}));
test.test_get_primes_suite(vector<int>({1,2,3,4,5}));

return 0;
}

• OO is for simulations and modelling, mathy and algorithmic code is much nicer pure imperative (or functional). Also finding the primes upto n is just (1..n).select(&:is_prime) or a sieve if performance is a concern. – Caridorc Aug 22 '15 at 17:18
• @Quill Thanks for the editing! (and sorry for my poor English expression...). I have added some context and feel free to rephrase them if needed. Thanks! – yvetterowe Aug 22 '15 at 22:31

## Namespaces

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred.

## Return

return 0; is a legacy from C. In C++, it's no longer required to write this manually at the end of main. The compiler will take care of returning 'normal' if no errors where thrown or other returns (like -1) are encountered.

## Naming

The following is confusing:

PrimeFinder test;
PrimeFinderTest test;


You have both multiple PrimeFinder around which you named test as a PrimeFinderTest named test. In all cases the variable name is not descriptive and together it's confusing.

## Loops

Do you have a particular reason why the following is a while loop?

            while(j <= n) {
if(j > n_) {
is_prime_[j] = false;
}
j += i;
}


A for loop would be more readable here.

Now we're talking about that loop anyway, only use one letter variables like i and j when iterating (if at all, those extra bytes for full names won't bite you). Here, you're using both n and n_ without documenting what they are. That's a maintainability trap.

There's no rule against trailing underscores (my personal preference is not to use them), but in this case the difference between n and n_ is not distinctive enough. n_ = n; is also a good indication your naming could be improved.