patterncppMajor

Prime sieve for all primes up to a number

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

numberprimesallsieveforprime

Problem

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  /* NULL */
#include  /* malloc, free */
#include  /* strcmp */
#include  /* std::istringstream */
#include  /* std::cout, std::cerr, std::endl */

/**
 * Returns the primes from 1 to  as a std::size_t* that ends with a 0.
 * NULL if  is negative or malloc or realloc returned NULL.
 */
std::size_t* prime_sieve(std::size_t limit) {
    if (limit > limit)) {
            std::cerr > 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:

Solution

Comments

Most people write bad comments.

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.

Your comments are bad.

#include  /* NULL */
#include  /* malloc, free */
#include  /* strcmp */
#include  /* std::istringstream */
#include  /* 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?

Headers

These are headers from the "C" language.

You should note this is a completely different language.

#include 
#include 
#include

There are C++ equivalent for these headers.

#include 
#include 
#include

Note most C headers ` have a C++ equivelent

.

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  as a std::size_t* that ends with a 0.
 * NULL if  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 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 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 underlyin

Code Snippets

#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 */

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

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

/**
 * 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);

Context

StackExchange Code Review Q#158150, answer score: 23

Revisions (0)

No revisions yet.