67 lines
1.6 KiB
C++
67 lines
1.6 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
|
|
int main()
|
|
{
|
|
const int limit = 1000000;
|
|
|
|
// find the prime numbers up to the limit
|
|
std::vector<bool> isprime(limit + 1, true);
|
|
isprime[0] = isprime[1] = false;
|
|
for (int p = 2; p * p <= limit; ++p)
|
|
{
|
|
if (isprime[p])
|
|
{
|
|
for (int i = p * p; i <= limit; i += p)
|
|
isprime[i] = false;
|
|
}
|
|
}
|
|
int largest_left = 0;
|
|
int largest_right = 0;
|
|
// find largest left truncatable prime
|
|
for (int p = limit; p >= 2; --p)
|
|
{
|
|
if (!isprime[p])
|
|
continue;
|
|
bool left_truncatable = true;
|
|
for (int n = 10, q = p; p > n; n *= 10)
|
|
{
|
|
if (!isprime[p % n] || q == p % n)
|
|
{
|
|
left_truncatable = false;
|
|
break;
|
|
}
|
|
q = p % n;
|
|
}
|
|
if (left_truncatable)
|
|
{
|
|
largest_left = p;
|
|
break;
|
|
}
|
|
}
|
|
// find largest right truncatable prime
|
|
for (int p = limit; p >= 2; --p)
|
|
{
|
|
if (!isprime[p])
|
|
continue;
|
|
bool right_truncatable = true;
|
|
for (int q = p/10; q > 0; q /= 10)
|
|
{
|
|
if (!isprime[q])
|
|
{
|
|
right_truncatable = false;
|
|
break;
|
|
}
|
|
}
|
|
if (right_truncatable)
|
|
{
|
|
largest_right = p;
|
|
break;
|
|
}
|
|
}
|
|
// write results to standard output
|
|
std::cout << "Largest left truncatable prime is " << largest_left << '\n';
|
|
std::cout << "Largest right truncatable prime is " << largest_right << '\n';
|
|
return 0;
|
|
}
|