Prime Sieve and brute force #2

Based on my previous attempt.

Prime Sieve and brute force

Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the primes and inc and the next value to look at. This way I can control accesses to isPrime() so it can not be called on values directly (as it makes the assumption you have already calculated all previous primes).

When my code is manipulating a potential prime it uses int as the type. If the code is working on the size of a container or index into a container directly then I use std::size_t.

I tried being consistent with my braces. But an if statement that just had a return inside looked so ugly with my standard braces.

if (<test>)
{
return;
}
// I know it only saves one line but that looks ugly and wasteful
if (<test>) {
return;
}

So I have kept them small but otherwise open/closing braces are aligned on the left.

se.h

#ifndef THORSANVIL_UTIL_SIEVE_ERATOSTHENES_H
#define THORSANVIL_UTIL_SIEVE_ERATOSTHENES_H

#include <vector>
#include <ostream>
#include <cstddef>

namespace ThorsAnvil
{

class SieveEratosthenes
{
public:
using Primes = std::vector<int>;

private:
static std::size_t constexpr maxSieveSize = 1024 * 1024;// approx 1M
Primes  primes;
int     inc;
int     next;

public:
SieveEratosthenes(int nTh);
Primes const& thePrimes()   const {return primes;}
int           count()       const {return primes.size();}
int           getCurrent()  const {return primes.back();}
int           getNext()           {calcNext(); return getCurrent();}
private:
void          calcNext();
bool          isPrime(int num);
int           getNextInc()        {inc = 6 - inc;return inc;}

friend std::ostream& operator<<(std::ostream& str, SieveEratosthenes const& data)
{
for(auto prime: data.primes) {
str << prime << " ";
}
return str;
}
};

}

#endif

se.cpp

#include "se.h"
#include <cmath>

using namespace ThorsAnvil;

SieveEratosthenes::SieveEratosthenes(int nTH)
: inc(4)
, next(5)
{
// We know we will have nTH primes.
primes.reserve(nTH);

// Take care of people trying to be silly and break things.
if (nTH <= 0) {
return;
}
primes.emplace_back(2);
if (nTH == 1) {
return;
}
primes.emplace_back(3);
if (nTH == 2) {
return;
}

// Estimate the sieve size we will need to find the nth prime.
// This is not exact so it will get you most of the way there.
// But this means you will have to brute force the rest.
// See the last loop in the constructor for that.
std::size_t sieveSize = nTH * std::log(nTH) / 2;  // Note: div 2 because we don't hold even numbers
sieveSize = std::min(sieveSize, maxSieveSize / sizeof(typename Primes::value_type) * CHAR_BIT);

// primeCandidates holds true/false for each potential prime candidate.
// The index represents the potential prime (index * 2 + 1)
// This allows us to ignore all multiple of 2
// max is one past the highest prime candidate we can test for and store in primeCandidates
std::vector<bool>   primeCandidates(sieveSize, true);

// We will use the technique of incrementing by 2 then 4 then 2 then 4
// This means skip all multiple of 2 and 3 automatically.
for(; next < sieveSize && nTH != count(); next += getNextInc())
{
std::size_t index = next/2;

// If we find a candidate that is valid then add it to results.
if (primeCandidates[index])
{
primes.push_back(next);

// Now strain out all multiple of the prime we just found.
for(index = next * next / 2; index < primeCandidates.size(); index += next)
{
primeCandidates[index] = false;
}
}
}

while(nTH != count())
{
calcNext();
}
}

void SieveEratosthenes::calcNext()
{
while(!isPrime(next))
{
next += getNextInc();
}
primes.push_back(next);
next += getNextInc();
}

bool SieveEratosthenes::isPrime(int num)
{
// Note: All primes less than num have already been found and stored in
//       the container primes. So this can only be used as part of
//       a brute force attack where you iterate up the number space and
//       store any found primes in prime. See: calcNext()
int max = std::sqrt(num);
for(auto const& prime: primes)
{
if (prime > max) {
return true;
}
if (num % prime == 0) {
return false;
}
}
return true;
}

main.cpp

Just a test to hang things from:

#include "se.h"
#include <string>
#include <iostream>

int main(int argc, char* argv[])
{
try
{
int find;
if ((argc != 2) || ((find = std::stoi(argv[1])) < 1))
{
throw std::runtime_error("Invalid Arguments");
}

using SE = ThorsAnvil::SieveEratosthenes;
SE  sieve(find);

std::cout << find << " prime: " << sieve.getCurrent() << "\n"
<< sieve << "\n";
}
catch(std::exception const& e)
{
std::cerr << "Exception: " << e.what() << "\n";
throw;
}
catch(...)
{
std::cerr << "Exception: Unknown Type\n";
throw;
}
}
• Our coding guidelines allow if (<test>) return; (but just in case of return, nothing else, e.g. not i++). That's the return early pattern. I'd personally not use it in general, but for Desktop C++ it's fine. May not be fine in embedded C++ environment where you have limited breakpoints – Thomas Weller Jun 6 at 18:27

At first, I was surprised by the use of a class here, but having read the code (and especially the main()), it clearly makes sense. It might be possible to make it more natural to use by providing a (const) iterator to access the values, rather than the getCurrent()/getNext() interface.

Consider defining the streaming operator in the implementation file. Not a big deal for this small program, but in well-used classes, it can make a difference, by allowing the header to include <iosfwd> instead of <ostream>. The former is intended to be faster for compilation.

A missing include in the implementation file: <climits> is required, for CHAR_BIT.

The class delegates all its resource management, smoothly satisfying the Rule of Zero. :-)

I don't see why we accept (signed) int as argument, if we're not allowing negative numbers. There's a serious bug anyway, in that we reserve(nTH) before we know it's not negative.

-Weffc++ warns about the default-initialised primes member. It's good to be explicit, and in this case it can simplify the constructor a little:

SieveEratosthenes::SieveEratosthenes(int nTH)
: inc(4)
, next(5)
, primes{2, 3}
{
// Take care of people trying to be silly and break things.
if (nTH <= 0) {
primes.clear()
return;
}
if (nTH <= 2) {
primes.resize(nTH);
return;
}

// We know we will have nTH primes.
primes.reserve(nTH);

std::vector<bool> optimises space at the expense of speed. We may find that std::vector<char> is more performant for reasonable sizes - have you done any benchmarks to justify this choice?