Stateful prime_numbers class for searching and storing primes

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
#include

template
/*
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 primes;
public:
using size_type = typename std::vector::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 > prim

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.

StackExchange Code Review Q#138573, answer score: 3