# Prime generator

I'm coming from a Python background(look at indentation :) ) and trying to learn basics of C++. I wrote a simple prime generator, I know there is better algorithms, but I want advices about coding style, inconsistencies, or better language use.

Here is my main.cpp:

#include <iostream>
#include "PrimeGenerator.h"

using namespace std;

int main(){
PrimeGenerator *generator;
generator = new PrimeGenerator();

for(int i=0;; i++){
cout<<generator->getPrimes()->back()<<endl;
}

delete generator; #I know this is unnecessary at the end of program, but I think it is a better practice.

return 0;
}


And PrimeGenerator.h:

#pragma once
#include <list>
#include <iostream>

typedef std::list<unsigned long long int> PrimeList;

class PrimeGenerator{

PrimeList *primes;

public:

PrimeGenerator();
~PrimeGenerator();

PrimeList *getPrimes();
};

PrimeGenerator::PrimeGenerator(){
primes = new PrimeList;

primes->push_back(2);
primes->push_back(3);
}

PrimeGenerator::~PrimeGenerator(){
delete primes;
}

unsigned long long int num = primes->back()+2;

while(true){
bool isPrime = true;

for(auto it=primes->begin(); it!=primes->end(); ++it){

if(*it > (num / 2))
break;

if((num % *it) == 0){
isPrime = false;
break;
}
}

if(isPrime){
primes->push_back(num);
break;
}

num += 2;
}
}

PrimeList *PrimeGenerator::getPrimes(){
return primes;
}


Your indentation style is unusual for C++. There are a variety of styles used in C++, I recommend you take a look at them, http://en.wikipedia.org/wiki/Indent_style, pick one you like. As it is you are combing elements of several styles. We don't need more indentation styles, so use a standard one, don't invent your own.

#include <iostream>
#include "PrimeGenerator.h"

using namespace std;


Many people use this, but I recommend against it. It looks doing a from std import * in python. I think its better to just use the prefix.

int main(){
PrimeGenerator *generator;
generator = new PrimeGenerator();


You can combine this into one line:

PrimeGenerator * generator = new PrimeGenerator();


You can also avoid using a pointer altogether and write:

PrimeGenerator generator;

for(int i=0;; i++){


I think you are missing the middle element, as it is this is an infinite loop

        generator->addPrime();
cout<<generator->getPrimes()->back()<<endl;


I'd add spaces around the <<

        }

delete generator; #I know this is unnecessary at the end of program, but I think it is a better practice.


If you use the pointerless version I suggested, it will automatically be destroyed at the end of main.

    return 0;
}

#pragma once


This may not work on all compilers, so be careful.

#include <list>
#include <iostream>

typedef std::list<unsigned long long int> PrimeList;


List is a linked list, unlike lists in python which are resizable arrays. Linked lists are almost always the wrong choice as a datastructure. Perhaps a vector would be better? Vectors act like python lists. unsigned long long int can be written as unsigned long long. You also repeat it often enough creating a typedef might be a good idea.

class PrimeGenerator{

PrimeList *primes;


Don't make this a pointer. Just use the object directly.

    public:

PrimeGenerator();
~PrimeGenerator();

PrimeList *getPrimes();
};

PrimeGenerator::PrimeGenerator(){
primes = new PrimeList;


If you avoid make primes a pointer like I suggest, this is unneccesary.

    primes->push_back(2);
primes->push_back(3);
}

PrimeGenerator::~PrimeGenerator(){
delete primes;
}


If you avoid making primes a pointer like I suggest, this is unneccesary.

void PrimeGenerator::addPrime(){

unsigned long long int num = primes->back()+2;

while(true){
bool isPrime = true;

for(auto it=primes->begin(); it!=primes->end(); ++it){

if(*it > (num / 2))
break;


This limitation isn't obvious, a comment explaining would be good.

            if((num % *it) == 0){


Operator precedence rules were defined to make sense, use them.

                isPrime = false;
break;
}
}

if(isPrime){
primes->push_back(num);
break;
}

num += 2;
}
}


bool isPrime = false;
unsigned long long int num = primes->back();
while(!isPrime)
{
num += 2;

for(auto it = primes->begin(); it != primes->end(); it++)
{
if(*it > num / 2)
{
break;
}

if( num % *it == 0 )
{
isPrime = false;
break;
}
}
}
primes->push_back(num);


I try to avoid using break when possible. Basically, I try to restrict to cases where it is skipping the rest of the loop as an optimisation. If the breaks were removed, the code would be valid but slower.

PrimeList *PrimeGenerator::getPrimes(){
return primes;
}

• Thank you. But, is there a way to skip the break's with that logic? And also, one more question, using "auto" is bad for my learning(backward compatiblity isn't a problem for me), or code? Aug 20, 2011 at 22:56
• @utdemir, sorry, I didn't understand either of your questions. Aug 20, 2011 at 22:59
• You said "I try to avoid using break when possible.". How? And I used auto it = primes->begin() in code, should I explicitly define iterator's type? Aug 20, 2011 at 23:06
• @utdemir, I showed how to eliminate one the breaks in your example. I think the other breaks are fine. That's a perfectly fine use of auto. The auto syntax was introduce partially to avoid having to write out types like that iterator. Aug 21, 2011 at 1:39

You don't need to manage resources manually. You are declaring a pointer to the new PrimeGenerator instance and releasing it at the end of the main function, but what happens if one of the calls inbetween (for example, addPrime()) fails? You end up with a memory leak.

PrimeGenerator *generator;
generator = new PrimeGenerator();
....
delete generator;


why don't you use

PrimeGenerator generator;
....


You don't need to use pointers in the PrimeGenerator class either.

class PrimeGenerator
{

PrimeList primes;

public:
PrimeGenerator();

const PrimeList& getPrimes() const {return primes;}
};

std::ostream& operator<<(std::ostream& stream, PrimeList const& value)
{
for (PrimeList::const_iterator it = value.begin(); it != value.end; it++)
{
stream << *it << endl;
}

return stream;
}

PrimeGenerator::PrimeGenerator()
{
primes.push_back(2);
primes.push_back(3);
}

int main()
{
PrimeGenerator generator;

for(int i = 0; i < 100; i++)
{
}
cout << generator.getPrimes();

return 0;
}

• Thank you. Am I understand right if I don't use pointers, will those objects destroyed at the end of their scope? If this is true, when should I use pointers, or new and delete? Aug 20, 2011 at 22:42
• Yes, the objects you've constructed will be destroyed at the end of the function you've constructed them in. As for the pointers, you should avoid using them in C++ unless it is absolutely necessary for some reason. Aug 20, 2011 at 22:56

It seems to me that prime number generation is really best represented as an algorithm. Rather than giving the client access to the class' internals I'd also prefer to send the results to an iterator. Finally, I'd prefer to producing a set of results over producing one result at a time.

As such, it seems like the interface should be something like:

template <class FwdIt>
void gen_primes(size_t num, FwdIt out);


If you wanted, for example, to generate the first 100 primes, you'd call it something like this:

std::vector<int> primes(100);

gen_primes(100, primes.begin());


Note that since it reuses the data in the output, it does require a forward iterator, not an output iterator, so you couldn't (for example) use std::back_inserter(primes).

Although I'd probably incorporate most of (for example) @Winston Ewert's suggestions, internally the code could remain at least reasonably close to what you already have.

I think the object-oriented design could be improved.

• PrimeGenerator is a tool to generate a linked list. Once you return a pointer to it, who knows what the caller will do with its contents? The caller could alter the list in a way that breaks subsequent calls to .addPrime().
• Primes are a notionally infinite list, so your class should try to create the illusion of an infinite list. Requiring the user to call .addPrime() is a chore that breaks that illusion.

It would be better if PrimeList were a self-managing read-only list of prime numbers, like this:

class PrimeList {
public:
PrimeList();

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

private:
std::vector<unsigned long long> knownPrimes;

void findMorePrimes();
};


Then your implementation of operator[] could call findMorePrimes() as needed behind the scenes.

The notion of an infinite list also frees you from the expectation that you should only add one prime number at a time to the list. Then, you would have the flexibility to find batches of prime numbers at a time, with likely improvements in performance.