Revision a57eab83-2e2c-4df0-8c7f-e584e0385752 - Code Review Stack Exchange

#Simple things
You've misspelt `std::size_t` in a couple of places. I find I often do that, particularly when I've been writing C as well.

#Conversion of primes table
I don't think there's a good reason to collapse `primesBoolArray` into a vector when it's perfectly usable as it is (and faster to use than a binary search). In fact, I'd go further, and make it live up to its name (since we always call the function with a constant):

 // Get an array of bool - containing true at the prime indexes
 template<std::size_t N>
 std::array<bool,N> primesUpto()
 {
 // Use the Sieve of Eratosthenes
 std::array<bool,N> primes;
 primes[0] = primes[1] = false;
 std::fill(primes.begin()+2, primes.end(), true);
 
 static const long long int sqrtLimit = std::sqrt(N) + 1;
 
 for (std::size_t i = 2; i < sqrtLimit; ++i)
 if (primes[i])
 for (std::size_t j = i+i; j < N; j += i)
 primes[j] = false;
 
 return primes;
 }

# String manipulation
We can use division to truncate numbers. Right to left is most obvious:

 for (; n; n/=10)
 test(n);

Left to right can be done like this:

 for (std::size_t x = 10; x < n; x*= 10)
 test(n%x);

This becomes

 template<std::size_t N>
 bool isTruncPrime(std::size_t n, const std::array<bool,N>& primes)
 {
 for (std::size_t x = 10; x < n; x*= 10)
 if (!primes[n%x]) return false;
 
 for (; n; n/=10)
 if (!primes[n]) return false;
 
 return true;
 }

These two changes reduce runtime on my system from **0.022** seconds to **0.007** seconds.

We can afford to search the whole problem space (assuming we already know there are no 7-digit truncatable primes):

 int main()
 {
 static const auto primes = primesUpto<1'000'000>();
 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<11)
 for (std::size_t n = 11; n < primes.size(); n += 2) {
 if (isTruncPrime(n, primes))
 sum += n;
 }
 
 std::cout << sum << "\n";
 }

This form allows us to parallelize the computation to (possibly) eke out a tiny bit more speed:

 #pragma omp parallel for reduction(+:sum)

On my system, this makes it much slower - you'd need a larger problem space to benefit, I think.

---
#Modified code
 #include <array>
 #include <algorithm>
 #include <cmath>
 #include <cstddef>

 // Get an array of bool - containing true at the prime indexes
 template<std::size_t N>
 constexpr std::array<bool,N> primesUpto()
 {
 // Use the Sieve of Eratosthenes
 std::array<bool,N> primes{};
 primes[0] = primes[1] = false;
 std::fill(primes.begin()+2, primes.end(), true);
 
 constexpr std::size_t sqrtLimit = std::sqrt(N) + 1;
 
 for (std::size_t i = 2; i < sqrtLimit; ++i)
 if (primes[i])
 for (std::size_t j = i+i; j < N; j += i)
 primes[j] = false;
 
 return primes;
 }
 
 template<std::size_t N>
 constexpr bool isTruncPrime(std::size_t n, const std::array<bool,N>& primes)
 {
 for (std::size_t x = 10; x < n; x*= 10)
 if (!primes[n%x]) return false;
 
 for (; n; n/=10)
 if (!primes[n]) return false;
 
 return true; // All truncated parts are prime, so the number is a truncatable prime
 }
 
 
 #include <iostream>
 int main()
 {
 static const auto primes = primesUpto<1'000'000>();
 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<11)
 for (std::size_t n = 11; n < primes.size(); n += 2) {
 if (isTruncPrime(n, primes))
 sum += n;
 }
 
 std::cout << sum << "\n";
 }