3
\$\begingroup\$

I tried writing a prime sieve that grows as needed. I've only just started learning C++ so any feedback on idioms is extra welcome!

The header:

#ifndef prime_sieve_h__
#define prime_sieve_h__

#include <vector>

class prime_sieve {
  private:
    std::vector<bool> prime;
    int upto;

    void size_up(int n);

  public:
    prime_sieve();
    prime_sieve(int n);

    bool is_prime(int n);
    bool operator[] (const int nIndex);
};

#endif

And the implementation:

#include <iostream>

#include "prime_sieve.h"

#define PRIME_SIEVE_DEFAULT_CAPACITY 1

prime_sieve::prime_sieve() : prime_sieve(PRIME_SIEVE_DEFAULT_CAPACITY) {}

prime_sieve::prime_sieve(int m) {
  int n = std::max(3, m); // Filling in three elements already.
  prime = std::vector<bool>(n, true);
  prime[0] = false;
  prime[1] = false;
  prime[2] = true;
  upto = 1;

  size_up(n);
}

void prime_sieve::size_up(int m) {
  if (upto * upto >= m) { return; } // Don't need to size up
  int p = upto * upto; // Previous size
  int newupto = upto;
  while (newupto * newupto < m) { newupto++; } // Need to size up
  int n = newupto * newupto; // Upto upto^2
  prime.resize(n + 1, true); // Get new elements ready

  // First sieve the lower primes again because the newest elements haven't been
  // checked for them yet.
  for (int i = 2; i < upto; ++i) {
    if (prime[i]) {
      for (int j = std::max(i * (p / i) + i, i + i); j <= n; j += i) {
        prime[j] = false;
      }
    }
  }

  // Then sieve the primes above what was already checked.
  int i;
  for (i = upto; i * i <= n; ++i) {
    if (prime[i]) {
      for (int j = i + i; j <= n; j += i){
        prime[j] = false;
      }
    }
  }
  upto = i - 1; // Counted one too many.
}

bool prime_sieve::is_prime(int n) {
  size_up(n);
  return prime[n];
}

bool prime_sieve::operator[] (const int n) {
  return is_prime(n);
}

How should I test this? The only thing I though of was to test some known cases.

\$\endgroup\$
3
\$\begingroup\$

upto is a redundant variable. It's hard for me to tell what it is you're actually using it for, but you're already keeping your sieve in a dynamic container that keeps track of its own size. prime.size() should be how many values you've sieved up to. I'm not entirely sure what you're using upto, but keeping track of redundant state is very error-prone!

namings

prime is not the best name for that container (or any container) - perhaps sieve? Also size_up() should be called resize() for consistency with other container types.

repetition

Your logic with the squares doesn't make sense to me. If you want to check the primality of n, you need to make sure that your container is just at least that size. So I would write the top something like:

void prime_sieve::resize(int n) {
    if (sieve.size() > n) return;

    size_t old = sieve.size();
    sieve.resize(n+1, true);

    // ...
}

Next, the important thing to see is that we have two largely identical loops. We iterate on i over some range, and then if sieve[i], we iterate over j in some range by steps of i up to n setting sieve[j] to false. As a function:

void prime_sieve::resieve(size_t from, size_t to, size_t jstart) {
    for (; from != to; ++from) {
        if (sieve[from]) {
            for (size_t j = std::max(jstart/from*from, from*from); j < sieve.size(); j += i) {
                sieve[j] = false;
            }
        }
    }
}

We can start at i^2 for j, since every lower multiple of i we already know isn't prime (because it's a multiple of some other number smaller than i and we've already done those). With that, our resize() function in its entirety is:

void prime_sieve::resize(int n) {
    if (sieve.size() > n) return;

    size_t old = sieve.size();
    sieve.resize(n+1, true);

    resieve(2, old, old); // from 2 to old, starting at old
    resieve(old, sieve.size(), 0); // from old to n
}

defining constants

If you're going to have a PRIME_SIEVE_DEFAULT_CAPACITY, it should be a static constexpr size_t, not a #define. Stay away from macros.

constructor

You have:

prime_sieve::prime_sieve(int m) {
  int n = std::max(3, m); // Filling in three elements already.
  prime = std::vector<bool>(n, true);
  prime[0] = false;
  prime[1] = false;
  prime[2] = true;
  upto = 1;

  size_up(n);
}

This is less than ideal - we're constructing the sieve then just reconstructing it anyway. Just do it with the right values outright:

prime_sieve::prime_sieve(int m)
: sieve(std::max(3, m), true)
{
    sieve[0] = sieve[1] = false;
    resieve(2, sieve.size(), 0); // now that we have this handy helper,
                                 // we can use it here!
}
\$\endgroup\$
  • \$\begingroup\$ What does prime_sieve::prime_sieve(int m) : sieve(std::max(3, m), true) do exactly? (again, new to c++) \$\endgroup\$ – Syd Kerckhove Sep 11 '15 at 14:25
1
\$\begingroup\$
#ifndef prime_sieve_h__
#define prime_sieve_h__

You are using a reserved name due to the double underscore; you should adjust your naming convention for header guards (e.g. only use a single trailing underscore).

The relevant passage from the C++11 standard, 17.6.4.3.2 [global.names], says

Certain sets of names and function signatures are always reserved to the implementation:

  • Each name that contains a double underscore _ _ or begins with an underscore followed by an uppercase letter (2.12) is reserved to the implementation for any use.
  • Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.
\$\endgroup\$
  • \$\begingroup\$ I would also note that macros are traditionally all uppercase to avoid clashes with other identifiers. \$\endgroup\$ – Martin York Sep 11 '15 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.