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