# Prime sieve for all primes up to a number

As a beginner to C++, I wanted to make something using what I was learning, so I did this to learn about arrays. This implements the Sieve of Eratosthenes to find the primes up to a limit.

I didn't use std::vector on purpose because I didn't really know how to use pointers. I want to know if I am using the pointers correctly and if my coding style is good.

#include <stdio.h> /* NULL */
#include <stdlib.h> /* malloc, free */
#include <string.h> /* strcmp */
#include <sstream> /* std::istringstream */
#include <iostream> /* std::cout, std::cerr, std::endl */

/**
* Returns the primes from 1 to <limit> as a std::size_t* that ends with a 0.
* NULL if <limit> is negative or malloc or realloc returned NULL.
*/
std::size_t* prime_sieve(std::size_t limit) {
if (limit < 0) {
return NULL;
}
if (limit < 2) {
// No primes less than 2
std::size_t* primes = (std::size_t*) malloc(sizeof(std::size_t));
primes[0] = 0;
return primes;
}
limit++;  // Add one so the last index was the old limit

// An array of bools where sieve[i] is false if i is prime
bool* sieve = (bool*) malloc(limit * sizeof(bool));
if (sieve == NULL) {
return NULL;
}

// An array holding the prime numbers. Ends with 0.
std::size_t* primes = (std::size_t*) malloc(sizeof(std::size_t));
if (primes == NULL) {
free(sieve);
return NULL;
}

// 0 and 1 are not prime.
sieve[0] = true;
sieve[1] = true;

std::size_t n = 0;

for (std::size_t i = 0; i < limit; i++) {
if (!sieve[i]) {
// i is prime

primes[n++] = i;

// Extend primes to be one longer
std::size_t* new_primes = (std::size_t*) realloc(primes, (n + 1) * sizeof(std::size_t));
if (new_primes == NULL) {
free(sieve);
free(primes);
return NULL;
}
primes = new_primes;

// Mark i*i..limit in sieve as not prime,
// as they are a multiple of i
for (std::size_t j = i * i; j < limit; j += i) {
sieve[j] = true;
}
}
}
free(sieve);
primes[n] = 0;
return primes;
}

int main(int argc, char* argv[]) {
if ((argc != 2) || (strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
std::cout << "usage: [-h] LIMIT\n\nFind prime numbers\npositional arguments:\n  LIMIT       upper limit for primes (positive integer or \"-\" to read from input)\n\noptional arguments:\n  -h, --help  show this help message and exit" << std::endl;
// If -h or --help, was a success and exit(0). Otherwise,
// there were too many or not enough arguments.
return argc == 1 ? 0 : 1;
}
std::size_t limit;
if (strcmp(argv[1], "-") == 0) {
// Read from stdin into a std::size_t
if (!(std::cin >> limit)) {
std::cerr << "Invalid integer given" << std::endl;
return 1;
}
} else {
// Read into limit as a string stream to convert to std::size_t
if (!((std::istringstream) argv[1] >> limit)) {
std::cerr << "Invalid integer given" << std::endl;
return 1;
}
}

if (limit < 0) {
std::cerr << "Invalid integer given" << std::endl;
return 1;
}

std::size_t* primes = prime_sieve(limit);
if (primes == NULL) {
// malloc or realloc returned NULL.
std::cerr << "Ran out of memory" << std::endl;
return 1;
}

std::size_t i = 0;
if (std::size_t prime = primes[i++]) {
// The first one has no space preceding it
std::cout << prime;
while (prime = primes[i++]) {
std::cout << ' ' << prime;
}
}
std::cout << std::endl;
free(primes);
return 0;
}


And these results:

~/primes\$ ./primes.out 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97


This is not meant to be extremely efficient, but here are the timings (taken from the real value from time):

10:              0.012s (avg. of 200)
100:             0.012s (avg. of 200)
1000 (1K):       0.013s (avg. of 200)
10000:           0.013s (avg. of 200)
100000:          0.017s (avg. of 200)
1000000 (1M):    0.062s (avg. of 200)
10000000:        0.542s (avg. of 100)
100000000:       8.457s (avg. of 10)
1000000000 (1G): 5m20.088s and 5m30.866s (325.477s, avg. of 2)

• I want to know if I am using the pointers correctly and if my coding style is good. those are contradicting statements. Sure you can be using pointers correctly but then your style is bad. Or you are not using pointers and your style is good. Modern C++ does not often use pointers except at the very lowest of levels. – Martin York Mar 18 '17 at 20:39
• @LokiAstari I meant something more like "If pointers correct (1st priority) and then if they are, the rest of the style is good", as I read conflicting things on style. – Artyer Mar 18 '17 at 20:40
• I got what you meant. But I am also going to point out why using pointers like this is bad. – Martin York Mar 18 '17 at 20:44

Things that should be commented are idea/decisions/why.

Writing comments that explain the code is horrible. This is because comments often fall out of date with the code, then you have to worry which is correct. Is the comment correct and the code is bad and thus I have a bug to fix, or os the code correct now I have to understand the code to re-write the comment.

Both of these situations is a waste of time.

#include <stdio.h> /* NULL */
#include <stdlib.h> /* malloc, free */
#include <string.h> /* strcmp */
#include <sstream> /* std::istringstream */
#include <iostream> /* std::cout, std::cerr, std::endl */


That is not all these headers have. Do I need to keep the comments up to date over time?

These are headers from the "C" language.
You should note this is a completely different language.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


There are C++ equivalent for these headers.

#include <cstdio>
#include <cstdlib>
#include <cstring>


Note most C headers <HEAD.h> have a C++ equivelent <cHEAD>.

By using these headers you put all the functionality they provide in the std namespace. The headers you use put the functionality in the global namespace (though implementations may also put the functionality in std). As a result your code below where you use std::X is very likely to fail on other compilers (or at least you can not guarantee it will compile out of the box).

### Design

Note: this is a good comment.

/**
* Returns the primes from 1 to <limit> as a std::size_t* that ends with a 0.
* NULL if <limit> is negative or malloc or realloc returned NULL.
*/


But the design is a bit shitty. I have to scan the prime array to find out how many I have this not very nice. Also it makes any code using it inefficient especially as that information is readily available.

### Ownership semantics

The huge difference between C and C++ is ownership semantics. Note: Ownership semantics is defining who owns a resource and therefore who is responsible for releasing the resource. Only the owner can/should release the resource.

The major pain point (source of bugs) in C is caused because there is no way at the language level to define ownership semantics of a resource. In C++ we have these semantics and thus have stopped using pointers (because these have no ownership associated with them).

So a C interface that looks like this:

std::size_t* prime_sieve(std::size_t limit);


The trouble here is I don't know who owns the pointer that is returned. Is it a pointer to a static array. Is it dynamically allocated. There is no way to know from the language level based on reading that interface.

In C++ it could look like this (probably not but steering clear of vector for you).

std::unique_ptr<std::size_t[]> prime_sieve(std::size_t limit);


This basically says I (the function) am returning an array the at I dynamically allocated internally. I am handing the ownership of this array back to you and thus it is your responsibility to delete it. Note: The object std::unique_ptr will deal with deleting it.

As a result C++ does not have the issues with memory leaks that languages like C has. It also has better garbage collection (its deterministic and fine grained) than languages like C# or Java.

This is all because of ownership semantics (and the concept of RAII).

### Stop using NULL

C++ has an explicit correctly types value for this: nullptr.

Unlike the macro NULL (that comes from the C language) the literal nullptr has an explicit type that does not get accidently converted to other types.

Thus it can not be used incorrectly.

### Stop using C casts

C++ has its own more refined casting tools.

static_cast<>()
const_cast<>()
reinterpret_cast<>()
dynamic_cast<>()


The problem with C casts are they are exceedingly dangerous. Basically you are telling the compiler to override the type system (designed to protect you) and do as you say (even if what you say is stupid).

But to compound this C casts are exceedingly hard to spot in the code. So even a good code review may miss very dangerous casts.

The C++ casts are designed to stand out. They can be just as dangerous as a C cast (though because they perform specific subset of operations each not quite) but because they stand out they are much easier to spot while reading the code and thus review and check that you have got correct.

If I see a reinterpret_cast<>() in the code I usually go WTF and start picking through that code with a fine comb.

### Stop using malloc/free/realloc

C++ has its own memory allocation functions that are built into the language.

        std::size_t* primes = (std::size_t*) malloc(sizeof(std::size_t));


In C++ we would use:

        std::size_t* primes = new std::size_t[1];


Actually since we want to define ownership semantics we would actually use:

        std::unique_ptr<std::size_t[]> primes(new std::size_t[1]);


The two dynamic memory allocation areas (HEAP for C and FreeStore for C++) are not guaranteed to be the same region (nor is the underlying implementation of memory layout). So memory allocated can not be free'd by the other system.

So using two different systems for memory allocation becomes dangerous as not only do you need to free the memory but you need to track which system of allocation was used to allocate the memory. A simpler solution is to just not use the dynamic memory allocation system of another language.

Which brings us around to vectors. Which does all the memory allocation in the background and you don't need to do it manually. Also as it acts just like an array it is just as easy to use as a pointer.

### RAII

Here is another example of problem with pointers.

    std::size_t* primes = (std::size_t*) malloc(sizeof(std::size_t));
if (primes == NULL) {
free(sieve);       // if primes fails I have to remember sieve!
return NULL;
}

/// and
std::size_t* new_primes = (std::size_t*) realloc(primes, (n + 1) * sizeof(std::size_t));

if (new_primes == NULL) {
free(sieve);
free(primes);
return NULL;
}


You have to remember to release them. The above code is correct. But basically you have to find every early return from a function and explicitly make sure that you have manually released all resources just before the return.

This is why a lot of C guidelines forbid early return (it's hard to validate that you got it all correct).

C++ introduced the concept of RAII that handles this automatically.

By using a locally scoped object the destructor of the object can release the resource when it goes out of scope (happens on function exit). So resources are automatically closed without need for the programmer to check every exit path from a function.

The standard has several types that help you do this for raw pointers. std::unique_ptr or std::shared_ptr but normally this is done as part of normal class creation. You make sure your object obeys the rule of 3/5 and then your resource are handled automatically (this is why vector is so useful all the memory management is wrapped up inside and you don't need to think about it).

This concept becomes even more important when you remember that C++ has exceptions and your function can exit because a function you called threw an exception which has cause the stack to unwind. The language guarantees that local objects destructor are called when stack is unwound thus RAII gurantess resource destruction even when exceptions are thrown.

Currently as your code stands it is not exception safe.

In C++ (unlike C) early return is not only embraced but encouraged.

### Reallocing every prime.

Sure you can do this.

            std::size_t* new_primes = (std::size_t*) realloc(primes, (n + 1) * sizeof(std::size_t));


But this is VERY inefficient. The most expensive parts of your code are calls to malloc and realloc the rest is trivial. And you make a call to realloc() for every new prime.

A better technique would be to allocate more space than you need and only realloc when you actually run out of space. A very common technique is to multiply the currently used space by 1.5.

This exponentially reduces the number of calls to realloc() though the cost is you have to keep track of two numbers now. The number of spaces used and the number of spaces allocated.

Which brings us back to vector which does this for you behind the scenes.

OK. This is a bit sloppy but I can live with it.

    if ((argc != 2) || (strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {


This is just horrible.

        std::cout << "usage: [-h] LIMIT\n\nFind prime numbers\npositional arguments:\n  LIMIT       upper limit for primes (positive integer or \"-\" to read from input)\n\noptional arguments:\n  -h, --help  show this help message and exit" << std::endl;


Never do things like this. This may be easy for the compiler to read but for us poor humans this is giberish. Take some time to make it human readable.

The most expensive part of system is the programmers who read the code. Don't break them with giberish.

### Prefer \n to std::end

    std::cout << std::endl;


The difference is that endl also forces a flush. This is basically never needed. The automatic flushing of the streams is nearly always better. The only thing this does is potentially make the code less efficient for flushing too much.

### Don't bother with return 0 in main

    return 0;


If your code never returns anything but 0 then it has become convention not to add the return 0 to main. This is an indication to a reader that this application will never indicate a failure to the OS.

### The dangers of unsigned

You should probably always use signed types when working with numbers (save unsigned types for bit fields).

Yes I know that the standard library uses unsigned types for std::size_t and stuff like that. But believe me the standards committee regrets that mistake and have publicly said so. BUT they are not going to change it (too late).

The problem comes from C (and thus C++) automatic integer conversions. If you pass a signed value to an unsigned parameter the compiler will silently do the conversion (even if the value is negative). The problem is you can not detect the conversion and your bounds checking will suffer:

std::size_t* prime_sieve(std::size_t limit) {

if (limit < 0) {   // This will never fire.
return NULL;   // As limit can never be negative.
}

// if you pass a negative value you are going to
// to do a lot of work as limit is probably a very large positive
// number in that situation.


But I can still call that function with a negative value:

prime_sieve(-1);


Will compile just as expected. Yet the test inside the function will never catch that -1.

if (!((std::istringstream) argv[1] >> limit)) {


Yes I can see what you are doing. But will everybody!

Casting a char const* to a stream (not correctly by the way). Then reading the value from the stream into limit and checking that the read worked in one statement.

Unfortunately you got it wrong. But it's still a valid statement.

What is happening here is you are taking the pointer and shifting the bits of the pointer right by limit (currently undefined). The resulting pointer is then cast to a string stream (creating a stringstream object). This is tested with the operator! and since you have not read from it will always return true.

This is a good point to advertize that you should increase your warning level well beyond normal. All warnings are logical errors in your thinking. Your compiled code should not generate any warnings.

I think the minimum warning flags should be:

g++ -Wall -Wextra --pedantic -Werror


### Small bug

while (prime = primes[i++]) {
^^^


This is caught by the compiler if you turn on warnings.

## Rewrite using pointers and RAII

#include <iostream>
#include <memory>
#include <sstream>

std::unique_ptr<int[]> prime_sieve(int limit)
{
if (limit < 0U) {
return std::unique_ptr<int[]>();
}
if (limit < 2U) {
// No primes less than 2
return std::unique_ptr<int[]>(new int[1]);
}
limit++;  // Add one so the last index was the old limit

// An array of bools where sieve[i] is false if i is prime
std::unique_ptr<bool> sieve(new bool[limit]);

// An array holding the prime numbers. Ends with 0.
int size    = 0;
int reserve = 50;
std::unique_ptr<int[]> primes(new int[reserve]);

// 0 and 1 are not prime.
sieve.get()[0] = true;
sieve.get()[1] = true;

for (int loop = 0; loop < limit; ++loop)
{
if (!sieve.get()[loop])
{
// i is prime

primes.get()[size++] = loop;

// Extend primes to be one longer
if (size+1 == reserve)
{
reserve *= 1.5;
std::unique_ptr<int[]> newPrimes(new int[reserve]);
std::copy(primes.get(), primes.get() + size, &newPrimes[0]);
using std::swap;
swap (primes, newPrimes);
}
// Mark i*i..limit in sieve as not prime,
// as they are a multiple of i
for (int j = loop * loop; j < limit; j += loop) {
sieve.get()[j] = true;
}
}
}
primes[size] = 0;
return std::move(primes);
}


## Rewrite using vector

std::vector<int> prime_sieve(int limit)
{
if (limit < 2U) {
// No primes less than 2
return std::vector<int>();
}
// An array of bools where sieve[i] is false if i is prime
std::vector<bool> sieve(limit, false);

// 0 and 1 are not prime.
sieve[0] = true;
sieve[1] = true;

std::vector<int> primes;
for (int loop = 0; loop < limit; ++loop)
{
if (!sieve[loop])
{
// loop is prime
primes.push_back(loop);

// Mark i*i..limit in sieve as not prime,
// as they are a multiple of i
for (int j = loop * loop; j < limit; j += loop) {
sieve[j] = true;
}
}
}
return primes;
}


timed:

                                Vector Code          Original Code
10                              0m0.014s             0m0.012s
100                             0m0.016s             0m0.019s
1000   1K                       0m0.015s             0m0.017s
10000                           0m0.016s             0m0.015s
100000                          0m0.013s             0m0.033s
1000000  1M                     0m0.022s             0m0.028s
10000000                        0m0.056s             0m0.161s
100000000                       0m0.667s             0m1.624s
1000000000  1G                  0m8.234s             0m18.266s

• Very informative. I will save your answer in my personal archive of good answers. – Gabriel Mar 19 '17 at 6:07
• How about using auto instead of explicit types for local declarations? – Tamoghna Chowdhury Mar 19 '17 at 8:57
• @TamoghnaChowdhury: Sure using auto is a helpful technique. – Martin York Mar 19 '17 at 9:10
• Would you consider incorporating that too into your answer? – Tamoghna Chowdhury Mar 19 '17 at 9:10
• @TamoghnaChowdhury: Where does it fit for this question. I don't see a place in the original question were auto would help. – Martin York Mar 19 '17 at 9:22