prime.cpp

#ifndef __PRIME_HPP
#define __PRIME_HPP

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

class PrimeCheck {
 public:
  PrimeCheck() :
      _current_limit(23),
      _known_primes({2, 3, 5, 7, 11, 13, 17, 19}) { }

  bool is_prime(long n) {
    if (n < _current_limit) {
      return binary_search(_known_primes.begin(), _known_primes.end(), n);
    }

    for (long candidate = _current_limit; candidate < (n + 1); ++candidate) {
      bool is_prime = true;
      for (auto p = _known_primes.begin(); p != _known_primes.end(); ++p) {
        const long maybe_factor = *p;
        if (candidate % maybe_factor == 0) {
          is_prime = false;
          break;
        } else if (maybe_factor * maybe_factor > candidate) {
          break;
        }
      }
      if (is_prime) {
        _known_primes.push_back(candidate);
      }
    }
    _current_limit = n + 1;
    return _known_primes.back() == n;
  }

  std::vector<long>::const_iterator primes_begin() const {
    return _known_primes.begin();
  }

  std::vector<long>::const_iterator primes_end() const {
    return _known_primes.end();
  }

  std::vector<long>::const_reverse_iterator primes_rbegin() const {
    return _known_primes.rbegin();
  }

  std::vector<long>::const_reverse_iterator primes_rend() const {
    return _known_primes.rend();
  }

  void dump() const {
    for (auto I = primes_begin(); I != primes_end(); ++I) {
      std::cout << *I << " ";
    }
    std::cout << std::endl;
  }

 private:
  long _current_limit;
  std::vector<long> _known_primes;
};

#endif