primes.hpp

View source code here on GitHub!

Includes

template<typename T>
class PrimeGenerator<T>
template<typename T>
PrimeGenerator<T> PrimeGenerator<T>()
template<typename T>
PrimeGenerator<T> primes<T>()

These constructors will return an infinite generator of prime numbers. Note, however, that it does not guard against overflow, so choose your type carefully.

template<typename T>
PrimeGenerator<T> PrimeGenerator<T>(T upper_limit)
template<typename T>
PrimeGenerator<T> primes_until<T>(T upper_limit)

These constructors will return a finite generator of prime numbers, going to upper_limit.

template<typename T>
T next()

Returns the next prime, or 0 if it is above the defined limit.

bool has_next()

Returns true if there is a next value to generate.

template<typename T>
class PrimeFactors
template<typename T>
PrimeFactors<T> PrimeFactors<T>(T upper_limit)
template<typename T>
PrimeFactors<T> prime_factors<T>(T upper_limit)

These constructors will return a finite generator of prime factors of target.

template<typename T>
T next()

Returns the next prime factor, or 0 if it is above the defined limit.

bool has_next()

Returns true if there is a next value to generate.

template<typename T>
T is_composite<T>(T target)

If target is composite, this returns its first prime factor (or -1). Otherwise returns 0.

template<typename T>
bool is_prime<T>(T target)

Tests if a given number is prime.

  1#pragma once
  2
  3#include <iostream>
  4#include <vector>
  5#include <map>
  6#include <limits>
  7#include <stdexcept>
  8
  9template<typename T>
 10class PrimeGenerator {
 11public:
 12    PrimeGenerator()
 13        : prime(T(0)), candidate(T(1) + T(1)), has_limit(false), limit(std::numeric_limits<T>::max()) {}
 14
 15    PrimeGenerator(T upper_limit)
 16        : prime(T(0)), candidate(T(1) + T(1)), has_limit(true), limit(upper_limit) {}
 17
 18    T next() {
 19        if (has_limit && prime >= limit) {
 20            sieve.clear();
 21            throw new std::runtime_error("Tried to exceed given limit (or limit of data type).");
 22        }
 23        prime = next_prime(candidate);
 24        candidate = prime + T(1);
 25        return prime;
 26    }
 27
 28    bool has_next() const {
 29        return !has_limit || prime < limit;
 30    }
 31
 32private:
 33    std::map<T, std::vector<T> > sieve;
 34    T prime;
 35    T candidate;
 36    bool has_limit;
 37    T limit;
 38
 39    T next_prime(T candidate) {
 40        typename std::map<T, std::vector<T> >::iterator it = sieve.find(candidate);
 41        if (it != sieve.end()) {
 42            const std::vector<T>& numbers = it->second;
 43            for (typename std::vector<T>::const_iterator num = numbers.begin(); num != numbers.end(); ++num) {
 44                const T num_val = *num;
 45                typename std::map<T, std::vector<T> >::iterator entry_it = sieve.find(candidate + num_val);
 46                if (entry_it != sieve.end())
 47                    entry_it->second.push_back(num_val);
 48                else {
 49                    std::vector<T> new_vec;
 50                    new_vec.push_back(num_val);
 51                    sieve[candidate + num_val] = new_vec;
 52                }
 53            }
 54            sieve.erase(candidate);
 55            return next_prime(candidate + T(1));
 56        }
 57        else {
 58            std::vector<T> vec;
 59            vec.push_back(candidate);
 60            sieve[candidate * candidate] = vec;
 61            return candidate;
 62        }
 63    }
 64};
 65
 66template<typename T>
 67PrimeGenerator<T> primes() {
 68    return PrimeGenerator<T>();
 69}
 70
 71template<typename T>
 72PrimeGenerator<T> primes_until(T x) {
 73    return PrimeGenerator<T>(x);
 74}
 75
 76template<typename T>
 77class PrimeFactors {
 78public:
 79    PrimeFactors(T target)
 80        : target(target), last_prime(T(std::numeric_limits<T>::max())), prime_gen(primes<T>()) {}
 81
 82    T next() {
 83        if (!has_next())
 84            throw new std::runtime_error("No more factors available.");
 85        if (std::numeric_limits<T>::min() < 0 && target < 0) {
 86            target = -target;
 87            return T(-1);
 88        }
 89        while (true) {
 90            if (target % last_prime == 0) {
 91                target /= last_prime;
 92                return last_prime;
 93            }
 94            last_prime = prime_gen.next();
 95        }
 96    }
 97
 98    bool has_next() const {
 99        return target != 1 && target != 0;
100    }
101
102private:
103    T target;
104    T last_prime;
105    PrimeGenerator<T> prime_gen;
106};
107
108template<typename T>
109PrimeFactors<T> prime_factors(T target) {
110    return PrimeFactors<T>(target);
111}
112
113template<typename T>
114T is_composite(T target) {
115    PrimeFactors<T> factors = prime_factors<T>(target);
116    if (!factors.has_next())
117        return target;
118    T first = factors.next();
119    if (first == target)
120        return T(0);
121     return first;
122}
123
124template<typename T>
125bool is_prime(T target) {
126    if (target < T(1) + T(1))
127        return false;
128    return is_composite<T>(target) == T(0);
129}

Tags: cpp-iterator, prime-number