Stateful prime_numbers class for searching and storing primes

Question

Title says the biggest part. The class is designed to be used to search for very big prime numbers, hence the element type is templated. The performance, neither in space nor time, is considered. Users are free to provide any type that supports required semantics. It also supports traverse performance of std::vector due to its implementation detail.

The class emulates container with constant elements. Manipulation is done through find_until(), find_n(), resize(), release().

Design Decisions:

I didn't use sqrt() since it would impose requirement on user provided type. I think that it would be slow on big integer type anyway.

The way container should be used is to fill once and traverse many times. It is similar to what std::vector does. Thus operator[] doesn't perform checks. at() function is provided for checked access. It resizes internal array of primes if index is out of bounds.

It doesn't scale on big input, so my particular concern is performance without changing the specification written in code:

#ifndef PRIME_NUMBERS_H
#define PRIME_NUMBERS_H

#include <vector>
#include <algorithm>

template <typename NumberType>
/*
    NumberType requires:
    Construction from unsigned int
    rule of three
    operator+(const NumberType&, unsgined int); or member +
    operator%(const NumberType&, const NumberType&); or member %
    Less than comparable;
    General semantic: integral positive number with enough range
*/
class prime_numbers
{
    std::vector<NumberType> primes;
public:
    using size_type = typename std::vector<NumberType>::size_type;

    prime_numbers(): 
        primes{2, 3, 5, 7}
    {

    }

    const NumberType& back() const
    {
        return primes.back();
    }

    const NumberType* data() const
    {
        return primes.data();
    }

    const NumberType& front() const
    {
        return primes.front();
    }

    const NumberType& operator[](size_type index)
    {
        return primes[index];
    }

    const NumberType& at(size_type index)
    {
        if (index > primes.size() - 1)
        {
            find_n(index - primes.size() + 1);
        }

        return primes[index];
    }

    auto begin() const
    {
        return primes.begin();
    }

    auto end() const
    {
        return primes.end();
    }

    auto rbegin() const
    {
        return primes.rbegin();
    }

    auto rend() const
    {
        return primes.rend();
    }

    void find_until(const NumberType& value)
    {
        for (auto i = primes.back() + 2; i <= value; i += 2)
        {
            if (is_prime(i))
            {
                primes.push_back(i);
            }
        }
    }

    void find_n(size_type count = 1)
    {
        size_type needed = primes.size() + count;

        for (auto i = primes.back() + 2; primes.size() < needed; i += 2)
        {
            if (is_prime(i))
            {
                primes.push_back(i);
            }
        }
    }

    size_type size() const
    {
        return primes.size();
    }

    void resize(size_type size)
    {
        if (size < primes.size())
        {
            primes.resize(size); //user wants to shrink, no seek needed
            return;
        }

        find_n(size - primes.size());
    }

    bool prime(const NumberType& number)
    {
        if (!(number < primes.back())) 
        // < is usually implemented first
        {
            find_until(number);
        }

        //primes are strictly in ascending order
        return std::binary_search(primes.begin(), primes.end(), number); 
    }

    std::vector<NumberType> release()
    {
        std::vector<NumberType> old{ 2, 3, 5, 7 };
        old.swap(primes);
        return old;
    }

private:
    bool is_prime(const NumberType& number)
    {
        for (const auto& prime : primes)
        {
            if (number % prime == 0)
            {
                return false;
            }
        }

        return true;
    }
};

#endif

Usage:

#include "prime_numbers.h"
#include <iostream>
#include <vector>

int main()
{
    prime_numbers<unsigned int> primes;

    primes.find_until(100);

    for (const auto& prime : primes)
    {
        std::cout << prime << '\n';
    }

    std::vector<unsigned int> copy(primes.release());

    for (auto it = copy.crbegin(); it != copy.crend(); ++it)
    {
        std::cout << *it << '\n';
    }
}

Unfortunately without concepts support it is impossible to express requirements on NumberType in code without comments.

Answer 1

I didn't use sqrt() since it would impose requirement on user provided type. I think that it would be slow on big integer type anyway.

You already require that % be implemented, so it is reasonable to expect that / be implemented. So

        for (const auto& prime : primes)
        {
            if (number % prime == 0)

Could become

        for (const auto& prime : primes)
        {
            if (number / prime < prime)
            {
                return true;
            }

            if (number % prime == 0)

Which has the same effect as checking if prime * prime > number or prime > sqrt(number).

Note that many implementations calculate both the remainder and the quotient at the same time, so the division can be done for free (since you already calculate the remainder). Even if not, it can be done for the same cost as the remainder. And there is a big difference between going to \$\sqrt{n}\$ and \$n\$.

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

There are four primes under ten, and twenty-one under a hundred. So would you prefer to do four pairs of operations? Or twenty-one single operations? Even counting the comparison as an operation, that's still only twelve compared to twenty-one.

See https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations if you'd like more information about comparing the time expense of various operations.