Solution to Project Euler Problem #37 in C++: Truncatable Primes I was recently looking at some of my old Project Euler solutions, and saw that my implementation for Problem 37 could be improved drastically.
The problem reads as follows:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Here is my C++ solution to the problem:
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;cmath&gt;
#include &lt;algorithm&gt;
#include &lt;cstdlib&gt;
#include &lt;string&gt;

std::vector&lt;long long int&gt; primesUpto(long long int limit) // Function that implements the Sieve of Eratosthenes
{
    std::vector&lt;bool&gt; primesBoolArray(limit, true);
    std::vector &lt;long long int&gt; result;
    
    primesBoolArray[0] = primesBoolArray[1] = false;
    long long int sqrtLimit = std::sqrt(limit) + 1;
    
    for (size_t i = 0; i &lt; sqrtLimit; ++i)
    {
        if (primesBoolArray[i])
        {
            for (size_t j = (2 * i); j &lt; limit; j += i)
            {
                primesBoolArray[j] = false;
            }
        }
    }
    for (size_t i = 0; i &lt; primesBoolArray.size(); ++i)
    {
        if (primesBoolArray[i])
        {
            result.push_back(i);
        }
    }
    return result;
}

bool isTruncPrime(long long int number, const std::vector&lt;long long int&gt;&amp; primeList)
{
    std::string numberString = std::to_string(number);
    for (int i = 1; i &lt; numberString.size(); ++i)
    {
        std::string truncLeft = numberString.substr(0, i); // The truncated prime from the left
        std::string truncRight = numberString.substr(i, numberString.size() - 1); // The truncated prime from the right
        if (!
            (
                std::binary_search(primeList.begin(), primeList.end(), std::atol(truncLeft.c_str())) &amp;&amp;
                std::binary_search(primeList.begin(), primeList.end(), std::atol(truncRight.c_str()))
            )   // If either of the two truncated sides are not prime
        )
        {
            return false;
        }
    }
    return true; // All truncated parts are prime, so the number is a truncatable prime
}

int main()
{
    const std::vector&lt;long long int&gt; primesUptoMillion = primesUpto(1'000'000LL); // Represents all the primes up to 1 million
    
    int numberTruncatablePrimes = 0;
    long long int currentNumber = 9; // 2, 3, 5, and 7 are not included in the search for truncatable primes
    long long int truncatablePrimeSum = 0;
    
    while (numberTruncatablePrimes != 11) 
    {
        if (
            std::binary_search(primesUptoMillion.begin(), primesUptoMillion.end(), currentNumber) &amp;&amp; // If the number itself is prime
            isTruncPrime(currentNumber, primesUptoMillion) // If the number is also a truncatable prime
        )
        {
            ++numberTruncatablePrimes; // Increase amount of truncatable primes
            truncatablePrimeSum += currentNumber; // Add the number's sum
        }
        currentNumber += 2; // Only odd numbers can be prime other than 2, so no need to look at every number
    }
    std::cout &lt;&lt; truncatablePrimeSum &lt;&lt; &quot;\n&quot;;
}

Here is how I run the code:
g++ Problem037.cpp -std=c++14 -O2

Here is code for execution, timing, and output:
$ time ./a.out
748317

real    0m0.042s
user    0m0.040s
sys     0m0.004s

Here are the things I want from this Code Review:

The function isTruncPrime() does a lot of string manipulation to verify its parameter. Is there a way to improve the algorithm?
While the code does run pretty quickly, is there any code that slows down the rest significantly that I could improve on?
Are there any better or more idiomatic ways to format/structure my program so it follows C++ style?
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.