Largest Prime Factor redux
Slight improvement in the sieve.
I doubt it is significant for max.

prime_table(integer num) {
    integer max = ceil(sqrt(num));
    std::vector&lt;char&gt; table(max, false);   // Making this char rather than bool
                                           // probably makes a tiny difference in speed.
                                           // Don't do an extra re-size do it all up
                                           // front in one allocation.

    // Initialize with the first 2 primes.
    // We don't need to mark multiples of 2 and 3 in the table as true.
    // because of the way we increment in the loop. We basically skip
    // all cells in table {for table[x] where (x%2 ==  0 || x%3 == 0)}
    // so we don't even consider multiples of 2 and 3.
    primes.push_back(2);
    primes.push_back(3);
    int inc = 4;

    // Increment by 2 then 4 (repeat)  (represented by `inc`)
    // This effectively ignores all multiples of 2 and 3.
    for (int i = 5; i &lt; max; i += inc) {
        inc = 6 - inc;
        if (!table[i]) {
            primes.push_back(i);
            for (integer temp = 2 * i; temp &lt; max; temp += i)
                table[temp] = true;
        }
    }
}


You needed the smallest prime here:

integer prime_factor(integer input) {
    for (int i = 0; primes[i] * primes[i] &lt;= input; i++)
        if (input % primes[i] == 0)
            return prime_factor(input / primes[i]);
    return input;
}


This may result in a lot of wasted work (if primes[0] works you did not need the other primes). To only do as much work as you need you may want to try and implement a lazy sieve. That way you only calculate as many primes as you actually need. That being said the sieve is already fast so the extra code and complexity may outweigh the advantages of being lazy.

But to facilitate your tests (to see if a lazy sieve is worthwhile) you could update the code to use std::begin() and std::end() on the primes container. That way it can use your current technique. But if you change the container for primes into something that calculates primes on the fly you don't need to modify your code.

integer prime_factor(integer input)
{
    for (auto prime: primes)   // use std::begin() and std::end in the background (I think)
    {
        if ((prime * prime) &gt; input) {
            break;
        }
        if (input % prime == 0) {
            return prime_factor(input / prime);
        }
    }
    return input;
}


Here is an attempt at a Lazy prime Sieve. Maybe that will help.

class LazyPrime
{
    std::vector&lt;integer&gt;    primes;
    integer                 max;
    std::vector&lt;char&gt;       table;
    integer                 inc;
    integer                 lastPrimeFound;

    struct LazyPrimeIterator
    {
        LazyPrime&amp;   parent;
        std::size_t  current;
        LazyPrimeIterator(LazyPrime&amp; p, int v) : parent(p), current(v) {}
        LazyPrimeIterator&amp; operator++()     {current = parent.next(++current);return *this;}
        integer            operator*()      {return parent.primes[current];}
        bool               operator!=(LazyPrimeIterator const&amp; rhs) const
        {return current != rhs.current;}
    };

    public:
        typedef LazyPrimeIterator           iterator;
        LazyPrime(integer num)
            : max(ceil(sqrt(num)))
            , table(max, false)
            , inc(2)
            , lastPrimeFound(5)
        {
            primes.push_back(2);
            primes.push_back(3);
            primes.push_back(5);
        }

        std::size_t next(std::size_t current)
        {
            if (current &lt; primes.size())
            {    return current;
            }

            // Assume primes retrieved in order.
            assert(current == primes.size());

            for (integer temp = 2 * lastPrimeFound; temp &lt; max; temp += lastPrimeFound){
                table[temp] = true;
            }

            // Increment by 2 then 4 (repeat)  (represented by `inc`)
            // This effectively ignores all multiples of 2 and 3.
            for (integer temp = lastPrimeFound + inc; temp &lt; max; temp += inc) {
                inc = 6 - inc;
                if (!table[temp]) {
                    lastPrimeFound = temp;
                    primes.push_back(lastPrimeFound);
                    return current;
                }
            }
            lastPrimeFound = max - inc;
            return -1; // Same as end.
        }

        iterator begin() { return LazyPrimeIterator(*this, 0);}
        iterator end()   { return LazyPrimeIterator(*this, -1);}
};