Solution to Project Euler Problem #37 in C++: Truncatable Primes
Warnings

It is usually a good idea to compile your code with all warnings enabled to see if anything is wrong. In your case, nothing really worrying but we may as well fix it.

Press ENTER or type command to continue
euler37.cpp: In function ‘std::vector&lt;long long int&gt; primesUpto(long long int)’:
euler37.cpp:16:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (size_t i = 0; i &lt; sqrtLimit; ++i)
                          ^
euler37.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (size_t j = (2 * i); j &lt; limit; j += i)
                                        ^
euler37.cpp: In function ‘bool isTruncPrime(long long int, const std::vector&lt;long long int&gt;&amp;)’:
euler37.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i &lt; numberString.size(); ++i)


You just need to use unsigned integers.

Algorithm

You could use a different approach to solve this problem. Instead of trying to find an efficient way to check if a number is a truncatable prime, you could try to find a way to generate them.
You could use the fact that the all right-truncable-primes of size n can be built easily from the list of right-truncable-primes of size n-1. The same logic applies to left-truncable-primes.

Here is a code example based on Toby Speight's code:

template&lt;std::size_t N&gt;
constexpr bool isLeftTruncPrime(std::size_t n, const std::array&lt;bool,N&gt;&amp; primes)
{
    for (std::size_t x = 10;  x &lt; n;  x*= 10)
        if (!primes[n%x]) return false;
    return true;
}

template&lt;std::size_t N&gt;
constexpr bool isRightTruncPrime(std::size_t n, const std::array&lt;bool,N&gt;&amp; primes)
{
    for (;  n;  n/=10)
        if (!primes[n]) return false;
    return true;
}

template&lt;std::size_t N&gt;
constexpr bool isTruncPrime(std::size_t n, const std::array&lt;bool,N&gt;&amp; primes)
{
    return isRightTruncPrime(n, primes) &amp;&amp; isLeftTruncPrime(n, primes);
}

#include &lt;iostream&gt;
int main()
{
    const auto limit = 1'000'000;
    static const auto primes = primesUpto&lt;limit&gt;();
    auto expected_sum = 748317ull;

    if (1)
    {
        auto sum = 0ull;
        // Start at 11, because single-digit numbers aren't truncatable
        // Advance by 2, because even numbers are non-prime (except 2, but 2&lt;11)
        for (std::size_t n = 11;  n &lt; primes.size();  n += 2) {
            if (isTruncPrime(n, primes))
                sum += n;
        }

        std::cout &lt;&lt; sum &lt;&lt; "\n";
        std::cout &lt;&lt; (sum == expected_sum) &lt;&lt; "\n";
    }

    if (0)
    {
        auto sum = 0ull;
        std::vector&lt;int&gt; truncprimes;
        truncprimes.push_back(2);
        truncprimes.push_back(3);
        truncprimes.push_back(5);
        truncprimes.push_back(7);

        while (!truncprimes.empty())
        {
            std::vector&lt;int&gt; truncprimes2;
            for (auto tp: truncprimes)
            {
                auto tens = tp*10;
                for (size_t d = 1; d &lt; 10; d+=2)
                {
                    auto n = tens + d;
                    if (n &lt; limit &amp;&amp; primes[n])
                    {
                        truncprimes2.push_back(n);
                        if (isLeftTruncPrime(n, primes) /*&amp;&amp; n &gt; 10 */)
                            sum += n;
                    }
                }
            }
            truncprimes = truncprimes2;
        }

        std::cout &lt;&lt; sum &lt;&lt; "\n";
        std::cout &lt;&lt; (sum == expected_sum) &lt;&lt; "\n";
    }
}


Then, because of the small amount of prime check we perform, pre-computing a sieve is not worth the pain. Thus, you don't even need to assume a maximum value. You don't even need to assume there will be 11 numbers found.

The new code is way faster than the original code:

bool isPrime(std::size_t num)
{
    if(num &lt;= 1) return false; // &lt;- 1 is not prime 
    for (std::size_t i = 2; i * i &lt;= num; i++)
        if (num % i == 0) return false;
    return true;
}

bool isLeftTruncPrime(std::size_t n)
{
    for (std::size_t x = 10; x &lt; n; x*= 10)
        if (!isPrime(n%x)) return false;
    return true;
}

#include &lt;iostream&gt;
int main()
{
    auto expected_sum = 748317ull;
    if (1)
    {
        auto sum = 0ull;
        std::vector&lt;int&gt; truncprimes;
        truncprimes.push_back(2);
        truncprimes.push_back(3);
        truncprimes.push_back(5);
        truncprimes.push_back(7);

        while (!truncprimes.empty())
        {
            std::cout &lt;&lt; truncprimes.size() &lt;&lt; "\n";
            std::vector&lt;int&gt; truncprimes2;
            for (auto tp: truncprimes)
            {
                auto tens = tp*10;
                for (size_t d = 1; d &lt; 10; d+=2)
                {
                    auto n = tens + d;
                    if (isPrime(n))
                    {
                        truncprimes2.push_back(n);
                        if (isLeftTruncPrime(n))
                            sum += n;
                    }
                }
            }
            truncprimes = truncprimes2;
        }

        std::cout &lt;&lt; sum &lt;&lt; "\n";
        std::cout &lt;&lt; (sum == expected_sum) &lt;&lt; "\n";
    }
}


Conclusion

I really like this problem and this solution because it shows that going straight into the Eratosthene sieve is not always the perfect solution.