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 <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <string>
std::vector<long long int> primesUpto(long long int limit) // Function that implements the Sieve of Eratosthenes
{
std::vector<bool> primesBoolArray(limit, true);
std::vector <long long int> result;
primesBoolArray[0] = primesBoolArray[1] = false;
long long int sqrtLimit = std::sqrt(limit) + 1;
for (size_t i = 0; i < sqrtLimit; ++i)
{
if (primesBoolArray[i])
{
for (size_t j = (2 * i); j < limit; j += i)
{
primesBoolArray[j] = false;
}
}
}
for (size_t i = 0; i < primesBoolArray.size(); ++i)
{
if (primesBoolArray[i])
{
result.push_back(i);
}
}
return result;
}
bool isTruncPrime(long long int number, const std::vector<long long int>& primeList)
{
std::string numberString = std::to_string(number);
for (int i = 1; i < 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())) &&
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<long long int> 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) && // 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 << truncatablePrimeSum << "\n";
}
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?
project-euler
tag? I tried to do so, but my edit was too short and wasn't applied. \$\endgroup\$