Truncatable primes: Difference between revisions
Added C++ solution
m (→{{header|REXX}}: simplified the code, added/changed whitespace and comments, used a template for the output section.) |
(Added C++ solution) |
||
Line 525:
}</lang>
<pre>Output: L 998443 R 739399 24 μs</pre>
=={{header|C++}}==
<lang cpp>#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;
}</lang>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Clojure}}==
| |||