Truncatable primes: Difference between revisions
Added Easylang
(New task and Python solution.) |
(Added Easylang) |
||
| (221 intermediate revisions by 80 users not shown) | |||
Line 1:
{{task|Prime Numbers}}
A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number
;Examples:
The number '''997''' is called a ''left-truncatable prime'' as the numbers '''997''', '''97''', and '''7''' are all prime.
The number '''7393''' is a ''right-truncatable prime'' as the numbers '''7393''', '''739''', '''73''', and '''7''' formed by removing digits from its right are also prime.
No zeroes are allowed in truncatable primes.
;Task:
The task is to find the largest left-truncatable and right-truncatable primes less than one million (base 10 is implied).
;Related tasks:
* [[Find largest left truncatable prime in a given base]]
* [[Sieve of Eratosthenes]]
;See also:
* [http://mathworld.wolfram.com/TruncatablePrime.html Truncatable Prime] from MathWorld.]
<br><br>
=={{header|11l}}==
{{trans|C}}
<syntaxhighlight lang="11l">V MAX_PRIME = 1000000
V primes = [1B] * MAX_PRIME
primes[0] = primes[1] = 0B
V i = 2
L i * i < MAX_PRIME
L(j) (i * i .< MAX_PRIME).step(i)
primes[j] = 0B
i++
L i < MAX_PRIME & !primes[i]
i++
F left_trunc(=n)
V tens = 1
L tens < n
tens *= 10
L n != 0
I !:primes[n]
R 0B
tens I/= 10
I n < tens
R 0B
n %= tens
R 1B
F right_trunc(=n)
L n != 0
I !:primes[n]
R 0B
n I/= 10
R 1B
L(n) (MAX_PRIME - 1 .< 0).step(-2)
I left_trunc(n)
print(‘Left: ’n)
L.break
L(n) (MAX_PRIME - 1 .< 0).step(-2)
I right_trunc(n)
print(‘Right: ’n)
L.break</syntaxhighlight>
{{out}}
<pre>
Left: 998443
Right: 739399
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Containers.Ordered_Sets;
procedure Truncatable_Primes is
package Natural_Set is new Ada.Containers.Ordered_Sets (Natural);
use Natural_Set;
Primes : Set;
function Is_Prime (N : Natural) return Boolean is
Position : Cursor := First (Primes);
begin
while Has_Element (Position) loop
if N mod Element (Position) = 0 then
return False;
end if;
Position := Next (Position);
end loop;
return True;
end Is_Prime;
function Is_Left_Trucatable_Prime (N : Positive) return Boolean is
M : Natural := 1;
begin
while Contains (Primes, N mod (M * 10)) and (N / M) mod 10 > 0 loop
M := M * 10;
if N <= M then
return True;
end if;
end loop;
return False;
end Is_Left_Trucatable_Prime;
function Is_Right_Trucatable_Prime (N : Positive) return Boolean is
M : Natural := N;
begin
while Contains (Primes, M) and M mod 10 > 0 loop
M := M / 10;
if M <= 1 then
return True;
end if;
end loop;
return False;
end Is_Right_Trucatable_Prime;
Position : Cursor;
begin
for N in 2..1_000_000 loop
if Is_Prime (N) then
Insert (Primes, N);
end if;
end loop;
Position := Last (Primes);
while Has_Element (Position) loop
if Is_Left_Trucatable_Prime (Element (Position)) then
Put_Line ("Largest LTP from 1..1000000:" & Integer'Image (Element (Position)));
exit;
end if;
Previous (Position);
end loop;
Position := Last (Primes);
while Has_Element (Position) loop
if Is_Right_Trucatable_Prime (Element (Position)) then
Put_Line ("Largest RTP from 1..1000000:" & Integer'Image (Element (Position)));
exit;
end if;
Previous (Position);
end loop;
end Truncatable_Primes;
</syntaxhighlight>
Sample output:
<pre>
Largest LTP from 1..1000000: 998443
Largest RTP from 1..1000000: 739399
</pre>
=={{header|ALGOL 68}}==
{{trans|C}} Note: This specimen retains the original [[#C|C]] coding style.
{{works with|ALGOL 68|Revision 1 - no extensions to language used.}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
<syntaxhighlight lang="algol68">#!/usr/local/bin/a68g --script #
PROC is prime = (INT n)BOOL:(
[]BOOL is short prime=(FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE);
IF n<=UPB is short prime THEN is short prime[n] # EXIT # ELSE
IF ( NOT ODD n | TRUE | n MOD 3 = 0 ) THEN FALSE # EXIT # ELSE
INT h := ENTIER sqrt(n)+3;
FOR a FROM 7 BY 6 WHILE a<h DO
IF ( n MOD a = 0 | TRUE | n MOD (a-2) = 0 ) THEN false exit FI
OD;
TRUE # EXIT #
FI
FI EXIT
false exit: FALSE
);
PROC string to int = (STRING in a)INT:(
FILE f; STRING a := in a; associate(f, a);
INT i; get(f, i); close(f);
i
);
PROC is trunc prime = (INT in n, PROC(REF STRING)VOID trunc)BOOL: (
INT n := in n;
STRING s := whole(n, 0);
IF char in string("0", NIL, s) THEN FALSE # EXIT #
ELSE
WHILE is prime(n) DO
s := whole(n, 0);
trunc(s);
IF UPB s = 0 THEN true exit FI;
n := string to int(s)
OD;
FALSE EXIT
true exit: TRUE
FI
);
PROC get trunc prime = (INT in n, PROC(REF STRING)VOID trunc)VOID:(
FOR n FROM in n BY -1 TO 1 DO
IF is trunc prime(n, trunc) THEN
printf(($g(0)l$, n));
break
FI
OD;
break: ~
);
main:(
INT limit = 1000000;
printf(($g g(0) gl$,"Highest left- and right-truncatable primes under ",limit,":"));
get trunc prime(limit, (REF STRING s)VOID: s := s[LWB s+1:]);
get trunc prime(limit, (REF STRING s)VOID: s := s[:UPB s-1]);
write("Press Enter");
read(newline)
)</syntaxhighlight>
Output:
<pre>
Highest left- and right-truncatable primes under 1000000:
998443
739399
Press Enter
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">leftTruncatable?: function [n][
every? map 0..(size s)-1 'z -> to :integer slice s z (size s)-1
=> prime?
]
rightTruncatable?: function [n][
every? map 0..(size s)-1 'z -> to :integer slice s 0 z
=> prime?
]
upperLimit: 999999
loop range upperLimit .step:2 0 'x [
s: to :string x
if and? not? contains? s "0"
leftTruncatable? x [
print ["highest left-truncatable:" x]
break
]
]
loop range upperLimit .step:2 0 'x [
s: to :string x
if and? not? contains? s "0"
rightTruncatable? x [
print ["highest right-truncatable:" x]
break
]
]</syntaxhighlight>
{{out}}
<pre>highest left-truncatable: 998443
highest right-truncatable: 739399</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">SetBatchLines, -1
MsgBox, % "Largest left-truncatable and right-truncatable primes less than one million:`n"
. "Left:`t" LTP(10 ** 6) "`nRight:`t" RTP(10 ** 6)
LTP(n) {
while n {
n--
if (!Instr(n, "0") && IsPrime(n)) {
Loop, % StrLen(n)
if (!IsPrime(SubStr(n, A_Index)))
continue, 2
break
}
}
return, n
}
RTP(n) {
while n {
n--
if (!IsPrime(SubStr(n, 1, 1)))
n -= 10 ** (StrLen(n) - 1)
if (!Instr(n, "0") && IsPrime(n)) {
Loop, % StrLen(n)
if (!IsPrime(SubStr(n, 1, A_Index)))
continue, 2
break
}
}
return, n
}
IsPrime(n) {
if (n < 2)
return, 0
else if (n < 4)
return, 1
else if (!Mod(n, 2))
return, 0
else if (n < 9)
return 1
else if (!Mod(n, 3))
return, 0
else {
r := Floor(Sqrt(n))
f := 5
while (f <= r) {
if (!Mod(n, f))
return, 0
if (!Mod(n, (f + 2)))
return, 0
f += 6
}
return, 1
}
}</syntaxhighlight>
'''Output:'''
<pre>Largest left-truncatable and right-truncatable primes less than one million:
Left: 998443
Right: 739399</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f TRUNCATABLE_PRIMES.AWK
BEGIN {
limit = 1000000
for (i=1; i<=limit; i++) {
if (is_prime(i)) {
prime_count++
arr[i] = ""
if (truncate_left(i) == 1) {
max_left = max(max_left,i)
}
if (truncate_right(i) == 1) {
max_right = max(max_right,i)
}
}
}
printf("1-%d: %d primes\n",limit,prime_count)
printf("largest L truncatable: %d\n",max_left)
printf("largest R truncatable: %d\n",max_right)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
function truncate_left(n) {
while (n != "") {
if (!(n in arr)) {
return(0)
}
n = substr(n,2)
}
return(1)
}
function truncate_right(n) {
while (n != "") {
if (!(n in arr)) {
return(0)
}
n = substr(n,1,length(n)-1)
}
return(1)
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
1-1000000: 78498 primes
largest L truncatable: 998443
largest R truncatable: 739399
</pre>
=={{header|Bracmat}}==
Primality test: In an attempt to compute the result of taking a (not too big, 2^32 or 2^64, depending on word size) number to a fractional power, Bracmat computes the prime factors of the number and checks whether the powers of prime factors make the fractional power go away. If the number is prime, the output of the computation is the same as the input.
<syntaxhighlight lang="bracmat">( 1000001:?i
& whl
' ( !i+-2:>0:?i
& !i:?L
& whl'(!L^1/2:#?^1/2&@(!L:% ?L))
& !L:~
)
& out$("left:" !i)
& 1000001:?i
& whl
' ( !i+-2:>0:?i
& !i:?R
& whl'(!R^1/2:#?^1/2&@(!R:?R %@))
& !R:~
)
& out$("right:" !i)
)</syntaxhighlight>
Output:
<pre>left: 998443
right: 739399</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PRIME 1000000
char *primes;
int n_primes;
/* Sieve. If we were to handle 10^9 range, use bit field. Regardless,
* if a large amount of prime numbers need to be tested, sieve is fast.
*/
void init_primes()
{
int j;
primes = malloc(sizeof(char) * MAX_PRIME);
memset(primes, 1, MAX_PRIME);
primes[0] = primes[1] = 0;
int i = 2;
while (i * i < MAX_PRIME) {
for (j = i * 2; j < MAX_PRIME; j += i)
primes[j] = 0;
while (++i < MAX_PRIME && !primes[i]);
}
}
int left_trunc(int n)
{
int tens = 1;
while (tens < n) tens *= 10;
while (n) {
if (!primes[n]) return 0;
tens /= 10;
if (n < tens) return 0;
n %= tens;
}
return 1;
}
int right_trunc(int n)
{
while (n) {
if (!primes[n]) return 0;
n /= 10;
}
return 1;
}
int main()
{
int n;
int max_left = 0, max_right = 0;
init_primes();
for (n = MAX_PRIME - 1; !max_left; n -= 2)
if (left_trunc(n)) max_left = n;
for (n = MAX_PRIME - 1; !max_right; n -= 2)
if (right_trunc(n)) max_right = n;
printf("Left: %d; right: %d\n", max_left, max_right);
return 0;
}</syntaxhighlight>output<syntaxhighlight lang="text">Left: 998443; right: 739399</syntaxhighlight>
Faster way of doing primality test for small numbers (1000000 isn't big), and generating truncatable primes bottom-up:
<syntaxhighlight lang="c">#include <stdio.h>
#define MAXN 1000000
int maxl, maxr;
int is_prime(int n)
{
int p;
if (n % 3 == 0) return 0;
for (p = 6; p * p <= n; p += 6)
if (!(n % (p + 1) && n % (p + 5)))
return 0;
return 1;
}
void left(int n, int tens)
{
int i, nn;
if (n > maxl) maxl = n;
if (n < MAXN / 10)
for (tens *= 10, i = 1; i < 10; i++)
if (is_prime(nn = i * tens + n))
left(nn, tens);
}
void right(int n)
{
int i, nn;
static int d[] = {1,3,7,9};
if (n > maxr) maxr = n;
if (n < MAXN / 10)
for (i = 1; i < 4; i++)
if (is_prime(nn = n * 10 + d[i])) right(nn);
}
int main(void)
{
left(3, 1); left(7, 1);
right(3); right(5); right(7);
printf("%d %d\n", maxl, maxr);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
998443 739399
</pre>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">using System; // 4790@3.6
using System.Collections.Generic;
class truncatable_primes
{
static void Main()
{
uint m = 1000000;
Console.Write("L " + L(m) + " R " + R(m) + " ");
var sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 1000; i > 0; i--) { L(m); R(m); }
Console.Write(sw.Elapsed); Console.Read();
}
static uint L(uint n)
{
n -= n & 1; n--;
for (uint d, d1 = 100; ; n -= 2)
{
while (n % 3 == 0 || n % 5 == 0 || n % 7 == 0) n -= 2;
if ((d = n % 10) == 3 || d == 7)
{
while (d1 < n && d < (d = n % d1) && isP(d)) d1 *= 10;
if (d1 > n && isP(n)) return n; d1 = 100;
}
}
}
static uint R(uint m)
{
var p = new List<uint>() { 2, 3, 5, 7 }; uint n = 20, np;
for (int i = 1; i < p.Count; n = 10 * p[i++])
{
if ((np = n + 1) >= m) break; if (isP(np)) p.Add(np);
if ((np = n + 3) >= m) break; if (isP(np)) p.Add(np);
if ((np = n + 7) >= m) break; if (isP(np)) p.Add(np);
if ((np = n + 9) >= m) break; if (isP(np)) p.Add(np);
}
return p[p.Count - 1];
}
static bool isP(uint n)
{
if (n < 7) return n == 2 || n == 3 || n == 5;
if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) return false;
for (uint r = (uint)Math.Sqrt(n), d = 7; d <= r; d += 30)
if (n % (d + 00) == 0 || n % (d + 04) == 0 ||
n % (d + 06) == 0 || n % (d + 10) == 0 ||
n % (d + 12) == 0 || n % (d + 16) == 0 ||
n % (d + 22) == 0 || n % (d + 24) == 0) return false;
return true;
}
}</syntaxhighlight>
<pre>Output: L 998443 R 739399 24 μs</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include "prime_sieve.hpp"
bool is_left_truncatable(const prime_sieve& sieve, int p) {
for (int n = 10, q = p; p > n; n *= 10) {
if (!sieve.is_prime(p % n) || q == p % n)
return false;
q = p % n;
}
return true;
}
bool is_right_truncatable(const prime_sieve& sieve, int p) {
for (int q = p/10; q > 0; q /= 10) {
if (!sieve.is_prime(q))
return false;
}
return true;
}
int main() {
const int limit = 1000000;
// find the prime numbers up to the limit
prime_sieve sieve(limit + 1);
int largest_left = 0;
int largest_right = 0;
// find largest left truncatable prime
for (int p = limit; p >= 2; --p) {
if (sieve.is_prime(p) && is_left_truncatable(sieve, p)) {
largest_left = p;
break;
}
}
// find largest right truncatable prime
for (int p = limit; p >= 2; --p) {
if (sieve.is_prime(p) && is_right_truncatable(sieve, p)) {
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;
}</syntaxhighlight>
Contents of prime_sieve.hpp:
<syntaxhighlight lang="cpp">#ifndef PRIME_SIEVE_HPP
#define PRIME_SIEVE_HPP
#include <algorithm>
#include <vector>
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class prime_sieve {
public:
explicit prime_sieve(size_t);
bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
/**
* Constructs a sieve with the given limit.
*
* @param limit the maximum integer that can be tested for primality
*/
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit);
is_prime_.resize(limit/2, true);
for (size_t p = 3; p * p <= limit; p += 2) {
if (is_prime_[p/2 - 1]) {
size_t inc = 2 * p;
for (size_t q = p * p; q <= limit; q += inc)
is_prime_[q/2 - 1] = false;
}
}
}
/**
* Returns true if the given integer is a prime number. The integer
* must be less than or equal to the limit passed to the constructor.
*
* @param n an integer less than or equal to the limit passed to the
* constructor
* @return true if the integer is prime
*/
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2)
return true;
if (n < 2 || n % 2 == 0)
return false;
return is_prime_.at(n/2 - 1);
}
#endif</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">(use '[clojure.contrib.lazy-seqs :only [primes]])
(def prime?
(let [mem (ref #{})
primes (ref primes)]
(fn [n]
(dosync
(if (< n (first @primes))
(@mem n)
(let [[mems ss] (split-with #(<= % n) @primes)]
(ref-set primes ss)
((commute mem into mems) n)))))))
(defn drop-lefts [n]
(let [dropl #(if (< % 10) 0 (Integer. (subs (str %) 1)))]
(->> (iterate dropl n)
(take-while pos? ,)
next)))
(defn drop-rights [n]
(->> (iterate #(quot % 10) n)
next
(take-while pos? ,)))
(defn truncatable-left? [n]
(every? prime? (drop-lefts n)))
(defn truncatable-right? [n]
(every? prime? (drop-rights n)))
user> (->> (for [p primes
:while (< p 1000000)
:when (not-any? #{\0} (str p))
:let [l? (if (truncatable-left? p) p 0)
r? (if (truncatable-right? p) p 0)]
:when (or l? r?)]
[l? r?])
((juxt #(apply max-key first %) #(apply max-key second %)) ,)
((juxt ffirst (comp second second)) ,)
(map vector ["left truncatable: " "right truncatable: "] ,))
(["left truncatable: " 998443] ["right truncatable: " 739399])</syntaxhighlight>
=={{header|CoffeeScript}}==
<syntaxhighlight lang="coffeescript"># You could have symmetric algorithms for max right and left
# truncatable numbers, but they lend themselves to slightly
# different optimizations.
max_right_truncatable_number = (n, f) ->
# This algorithm only evaluates 37 numbers for primeness to
# get the max right truncatable prime < 1000000. Its
# optimization is that it prunes candidates for
# the first n-1 digits before having to iterate through
# the 10 possibilities for the last digit.
if n < 10
candidate = n
while candidate > 0
return candidate if f(candidate)
candidate -= 1
else
left = Math.floor n / 10
while left > 0
left = max_right_truncatable_number left, f
right = 9
while right > 0
candidate = left * 10 + right
return candidate if candidate <= n and f(candidate)
right -= 1
left -= 1
throw Error "none found"
max_left_truncatable_number = (max, f) ->
# This is a pretty straightforward countdown. The first
# optimization here would probably be to cache results of
# calling f on small numbers.
is_left_truncatable = (n) ->
candidate = 0
power_of_ten = 1
while n > 0
r = n % 10
return false if r == 0
n = Math.floor n / 10
candidate = r * power_of_ten + candidate
power_of_ten *= 10
return false unless f(candidate)
true
do ->
n = max
while n > 0
return n if is_left_truncatable n, f
n -= 1
throw Error "none found"
is_prime = (n) ->
return false if n == 1
return true if n == 2
for d in [2..n]
return false if n % d == 0
return true if d * d >= n
console.log "right", max_right_truncatable_number(999999, is_prime)
console.log "left", max_left_truncatable_number(999999, is_prime)
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee truncatable_prime.coffee
right 739399
left 998443
</syntaxhighlight>
=={{header|Common Lisp}}==
<syntaxhighlight lang="lsip">
(defun start ()
(format t "Largest right-truncatable ~a~%" (max-right-truncatable))
(format t "Largest left-truncatable ~a~%" (max-left-truncatable)))
(defun max-right-truncatable ()
(loop for el in (6-digits-R-truncatables)
maximizing el into max
finally (return max)))
(defun 6-digits-R-truncatables (&optional (lst '(2 3 5 7)) (n 5))
(if (zerop n)
lst
(6-digits-R-truncatables (R-trunc lst) (- n 1))))
(defun R-trunc (lst)
(remove-if (lambda (x) (not (primep x)))
(loop for el in lst
append (mapcar (lambda (x) (+ (* 10 el) x)) '(1 3 7 9)))))
(defun max-left-truncatable ()
(loop for el in (6-digits-L-truncatables)
maximizing el into max
finally (return max)))
(defun 6-digits-L-truncatables (&optional (lst '(3 7)) (n 5))
(if (zerop n)
lst
(6-digits-L-truncatables (L-trunc lst (- 6 n)) (- n 1))))
(defun L-trunc (lst n)
(remove-if (lambda (x) (not (primep x)))
(loop for el in lst
append (mapcar (lambda (x) (+ (* (expt 10 n) x) el)) '(1 2 3 4 5 6 7 8 9)))))
(defun primep (n)
(primep-aux n 2))
(defun primep-aux (n d)
(cond ((> d (sqrt n)) t)
((zerop (rem n d)) nil)
(t (primep-aux n (+ d 1)))))
</syntaxhighlight>
{{out}}
<pre>Largest right-truncatable 739399
Largest left-truncatable 998443</pre>
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio, std.math, std.string, std.conv, std.algorithm,
std.range;
bool isPrime(in int n) pure nothrow {
if (n <= 1)
return false;
foreach (immutable i; 2 .. cast(int)sqrt(real(n)) + 1)
if (!(n % i))
return false;
return true;
}
bool isTruncatablePrime(bool left)(in int n) pure {
immutable s = n.text;
if (s.canFind('0'))
return false;
foreach (immutable i; 0 .. s.length)
static if (left) {
if (!s[i .. $].to!int.isPrime)
return false;
} else {
if (!s[0 .. i + 1].to!int.isPrime)
return false;
}
return true;
}
void main() {
enum n = 1_000_000;
writeln("Largest left-truncatable prime in 2 .. ", n, ": ",
iota(n, 1, -1).filter!(isTruncatablePrime!true).front);
writeln("Largest right-truncatable prime in 2 .. ", n, ": ",
iota(n, 1, -1).filter!(isTruncatablePrime!false).front);
}</syntaxhighlight>
{{out}}
<pre>Largest left-truncatable prime in 2 .. 1000000: 998443
Largest right-truncatable prime in 2 .. 1000000: 739399</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
procedure TruncatablePrimes(Memo: TMemo);
var Sieve: TPrimeSieve;
var I,P: integer;
function IsLeftTruncatable(P: integer): boolean;
{A prime is Left truncatable, if you can remove digits}
{one at a time from the left and it is still prime}
var S: string;
var P2: integer;
begin
Result:=False;
{Conver number to string}
S:=IntToStr(P);
{Delete one char from the left}
Delete(S,1,1);
while Length(S)>0 do
begin
{Zeros no allowed}
if S[1]='0' then exit;
{Convert back to number}
P2:=StrToInt(S);
{Exit if it is not prime}
if not Sieve.Flags[P2] then exit;
{Delete next char from left}
Delete(S,1,1);
end;
{If all truncated numbers are prime}
Result:=True;
end;
function IsRightTruncatable(P: integer): boolean;
{A prime is right truncatable, if you can remove digits}
{one at a time from the right and it is still prime}
var S: string;
var P2: integer;
begin
Result:=False;
{Conver number to string}
S:=IntToStr(P);
{Delete one char from the right}
Delete(S,Length(S),1);
while Length(S)>0 do
begin
{No zeros allowed}
if S[1]='0' then exit;
{Convert back to number}
P2:=StrToInt(S);
{exit if it is not prime}
if not Sieve.Flags[P2] then exit;
{Delete next char from the right}
Delete(S,Length(S),1);
end;
{If all truncated numbers are prime}
Result:=True;
end;
begin
Sieve:=TPrimeSieve.Create;
try
{Look at primes under 1 million}
Sieve.Intialize(1000000);
{Look for the highest Left Truncatable prime}
{Test all primes from 1 million down}
for I:=Sieve.PrimeCount-1 downto 0 do
begin
P:=Sieve.Primes[I];
{The first number that is Left Truncatable, will be the highest}
if IsLeftTruncatable(P) then
begin
Memo.Lines.Add(IntToStr(P));
break;
end;
end;
{Look for the highest Right Truncatable prime}
{Test all primes from 1 million down}
for I:=Sieve.PrimeCount-1 downto 0 do
begin
P:=Sieve.Primes[I];
if IsRightTruncatable(P) then
begin
Memo.Lines.Add(IntToStr(P));
break;
end;
end;
finally Sieve.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Largest Left Truncatable Prime: 998443
Largest Right Truncatable Prime: 739399
Elapsed Time: 14.666 ms.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func isright h .
while h > 0
if isprim h = 0
return 0
.
h = h div 10
.
return 1
.
func isleft h .
d = pow 10 (floor log10 h)
while h > 0
if isprim h = 0
return 0
.
if h div d = 0
return 0
.
h = h mod d
d /= 10
.
return 1
.
p = 999999
while isleft p = 0
p -= 2
.
print p
p = 999999
while isright p = 0
p -= 2
.
print p
</syntaxhighlight>
{{out}}
<pre>
998443
739399
</pre>
=={{header|EchoLisp}}==
<syntaxhighlight lang="lisp">
;; does p include a 0 in its decimal representation ?
(define (nozero? n) (= -1 (string-index (number->string n) "0")))
;; right truncate : p and successive quotients by 10 (integer division) must be primes
(define (right-trunc p) (unless (zero? p)
(and (prime? p) (right-trunc (quotient p 10)))))
(remember 'right-trunc)
;; left truncate : p and successive modulo by 10, 100, .. must be prime
(define (left-trunc p (mod 1000000))
(unless (< mod 1)
(and (prime? p) (nozero? p) (left-trunc (modulo p mod) (/ mod 10)))))
;; start from 999999. stop on first found
(define (fact-trunc trunc)
(for ((p (in-range 999999 100000 -1))) #:break (when (trunc p) (writeln p) #t)))
</syntaxhighlight>
Output:
<syntaxhighlight lang="lisp">
(fact-trunc left-trunc)
998443
(fact-trunc right-trunc)
739399
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
create
make
feature
make
do
io.put_string ("Largest right truncatable prime: " + find_right_truncatable_primes.out)
io.new_line
io.put_string ("Largest left truncatable prime: " + find_left_truncatable_primes.out)
end
find_right_truncatable_primes: INTEGER
-- Largest right truncatable prime below 1000000.
local
i, maybe_prime: INTEGER
found, is_one: BOOLEAN
do
from
i := 999999
until
found
loop
is_one := True
from
maybe_prime := i
until
not is_one or maybe_prime.out.count = 1
loop
if maybe_prime.out.has ('0') or maybe_prime.out.has ('2') or maybe_prime.out.has ('4') or maybe_prime.out.has ('6') or maybe_prime.out.has ('8') then
is_one := False
else
if not is_prime (maybe_prime) then
is_one := False
elseif is_prime (maybe_prime) and maybe_prime.out.count > 1 then
maybe_prime := truncate_right (maybe_prime)
end
end
end
if is_one then
found := True
Result := i
end
i := i - 2
end
ensure
Result_is_smaller: Result < 1000000
end
find_left_truncatable_primes: INTEGER
-- Largest left truncatable prime below 1000000.
local
i, maybe_prime: INTEGER
found, is_one: BOOLEAN
do
from
i := 999999
until
found
loop
is_one := True
from
maybe_prime := i
until
not is_one or maybe_prime.out.count = 1
loop
if not is_prime (maybe_prime) then
is_one := False
elseif is_prime (maybe_prime) and maybe_prime.out.count > 1 then
if maybe_prime.out.at (2) = '0' then
is_one := False
else
maybe_prime := truncate_left (maybe_prime)
end
end
end
if is_one then
found := True
Result := i
end
i := i - 2
end
ensure
Result_is_smaller: Result < 1000000
end
feature {NONE}
is_prime (n: INTEGER): BOOLEAN
--Is 'n' a prime number?
require
positiv_input: n > 0
local
i: INTEGER
max: REAL_64
math: DOUBLE_MATH
do
create math
if n = 2 then
Result := True
elseif n <= 1 or n \\ 2 = 0 then
Result := False
else
Result := True
max := math.sqrt (n)
from
i := 3
until
i > max
loop
if n \\ i = 0 then
Result := False
end
i := i + 2
end
end
end
truncate_left (n: INTEGER): INTEGER
-- 'n' truncated by one digit from the left side.
require
truncatable: n.out.count > 1
local
st: STRING
do
st := n.out
st.remove_head (1)
Result := st.to_integer
ensure
Result_truncated: Result.out.count = n.out.count - 1
end
truncate_right (n: INTEGER): INTEGER
-- 'n' truncated by one digit from the right side.
require
truncatable: n.out.count > 1
local
st: STRING
do
st := n.out
st.remove_tail (1)
Result := st.to_integer
ensure
Result_truncated: Result.out.count = n.out.count - 1
end
end
</syntaxhighlight>
{{out}}
<pre>
Largest right truncatable prime: 739399
Largest left truncatable prime: 999431
</pre>
=={{header|Elena}}==
ELENA 6.x :
<syntaxhighlight lang="elena">import extensions;
const MAXN = 1000000;
extension mathOp
{
isPrime()
{
int n := cast int(self);
if (n < 2) { ^ false };
if (n < 4) { ^ true };
if (n.mod(2) == 0) { ^ false };
if (n < 9) { ^ true };
if (n.mod(3) == 0) { ^ false };
int r := n.sqrt();
int f := 5;
while (f <= r)
{
if ((n.mod(f) == 0) || (n.mod(f + 2) == 0))
{ ^ false };
f := f + 6
};
^ true
}
isRightTruncatable()
{
int n := self;
while (n != 0)
{
ifnot (n.isPrime())
{ ^ false };
n := n / 10
};
^ true
}
isLeftTruncatable()
{
int n := self;
int tens := 1;
while (tens < n)
{ tens := tens * 10 };
while (n != 0)
{
ifnot (n.isPrime())
{ ^ false };
tens := tens / 10;
n := n - (n / tens * tens)
};
^ true
}
}
public program()
{
var n := MAXN;
var max_lt := 0;
var max_rt := 0;
while (max_lt == 0 || max_rt == 0)
{
if(n.toString().indexOf("0") == -1)
{
if ((max_lt == 0) && (n.isLeftTruncatable()))
{
max_lt := n
};
if ((max_rt == 0) && (n.isRightTruncatable()))
{
max_rt := n
}
};
n := n - 1
};
console.printLine("Largest truncable left is ",max_lt);
console.printLine("Largest truncable right is ",max_rt);
console.readChar()
}</syntaxhighlight>
{{out}}
<pre>
Largest truncable left is 998443
Largest truncable right is 739399
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
<syntaxhighlight lang="elixir">defmodule Prime do
defp left_truncatable?(n, prime) do
func = fn i when i<=9 -> 0
i -> to_string(i) |> String.slice(1..-1) |> String.to_integer end
truncatable?(n, prime, func)
end
defp right_truncatable?(n, prime) do
truncatable?(n, prime, fn i -> div(i, 10) end)
end
defp truncatable?(n, prime, trunc_func) do
if to_string(n) |> String.match?(~r/0/),
do: false,
else: trunc_loop(trunc_func.(n), prime, trunc_func)
end
defp trunc_loop(0, _prime, _trunc_func), do: true
defp trunc_loop(n, prime, trunc_func) do
if elem(prime,n), do: trunc_loop(trunc_func.(n), prime, trunc_func), else: false
end
def eratosthenes(limit) do # descending order
Enum.to_list(2..limit) |> sieve(:math.sqrt(limit), [])
end
defp sieve([h|_]=list, max, sieved) when h>max, do: Enum.reverse(list, sieved)
defp sieve([h | t], max, sieved) do
list = for x <- t, rem(x,h)>0, do: x
sieve(list, max, [h | sieved])
end
defp prime_table(_, [], list), do: [false, false | list]
defp prime_table(n, [n|t], list), do: prime_table(n-1, t, [true|list])
defp prime_table(n, prime, list), do: prime_table(n-1, prime, [false|list])
def task(limit \\ 1000000) do
prime = eratosthenes(limit)
prime_tuple = prime_table(limit, prime, []) |> List.to_tuple
left = Enum.find(prime, fn n -> left_truncatable?(n, prime_tuple) end)
IO.puts "Largest left-truncatable prime : #{left}"
right = Enum.find(prime, fn n -> right_truncatable?(n, prime_tuple) end)
IO.puts "Largest right-truncatable prime: #{right}"
end
end
Prime.task</syntaxhighlight>
{{out}}
<pre>
Largest left-truncatable prime : 998443
Largest right-truncatable prime: 739399
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="text">USING: formatting fry grouping.extras kernel literals math
math.parser math.primes sequences ;
IN: rosetta-code.truncatable-primes
CONSTANT: primes $[ 1,000,000 primes-upto reverse ]
: number>digits ( n -- B{} ) number>string string>digits ;
: no-zeros? ( seq -- ? ) [ zero? not ] all? ;
: all-prime? ( seq -- ? ) [ prime? ] all? ;
: truncate ( seq quot -- seq' ) call( seq -- seq' )
[ 10 digits>integer ] map ;
: truncate-right ( seq -- seq' ) [ head-clump ] truncate ;
: truncate-left ( seq -- seq' ) [ tail-clump ] truncate ;
: truncatable-prime? ( n quot -- ? ) [ number>digits ] dip
'[ @ all-prime? ] [ no-zeros? ] bi and ; inline
: right-truncatable-prime? ( n -- ? ) [ truncate-right ]
truncatable-prime? ;
: left-truncatable-prime? ( n -- ? ) [ truncate-left ]
truncatable-prime? ;
: find-truncatable-primes ( -- ltp rtp )
primes [ [ left-truncatable-prime? ] find nip ]
[ [ right-truncatable-prime? ] find nip ] bi ;
: main ( -- ) find-truncatable-primes
"Left: %d\nRight: %d\n" printf ;
MAIN: main</syntaxhighlight>
{{out}}
<pre>
Left: 998443
Right: 739399
</pre>
=={{header|Forth}}==
The prime sieve code is borrowed from [[Sieve of Eratosthenes#Forth]].
<syntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
: sieve ( n -- )
here over erase
0 notprime!
1 notprime!
2
begin
2dup dup * >
while
dup prime? if
2dup dup * do
i notprime!
dup +loop
then
1+
repeat
2drop ;
: left_truncatable_prime? ( n -- flag )
dup prime? invert if
drop false exit
then
dup >r
10
begin
2dup >
while
2dup mod
dup r> = if
2drop drop false exit
then
dup prime? invert if
2drop drop false exit
then
>r
10 *
repeat
2drop rdrop true ;
: right_truncatable_prime? ( n -- flag )
dup prime? invert if
drop false exit
then
begin
10 / dup 0 >
while
dup prime? invert if
drop false exit
then
repeat
drop true ;
: max_left_truncatable_prime ( n -- )
begin
dup 0 >
while
dup left_truncatable_prime? if . cr exit then
1-
repeat drop ;
: max_right_truncatable_prime ( n -- )
begin
dup 0 >
while
dup right_truncatable_prime? if . cr exit then
1-
repeat drop ;
1000000 constant limit
limit 1+ sieve
." Largest left truncatable prime: "
limit max_left_truncatable_prime
." Largest right truncatable prime: "
limit max_right_truncatable_prime
bye</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime: 998443
Largest right truncatable prime: 739399
</pre>
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
<syntaxhighlight lang="fortran">module primes_mod
implicit none
logical, allocatable :: primes(:)
contains
subroutine Genprimes(parr)
logical, intent(in out) :: parr(:)
integer :: i
! Prime sieve
parr = .true.
parr (1) = .false.
parr (4 : size(parr) : 2) = .false.
do i = 3, int (sqrt (real (size(parr)))), 2
if (parr(i)) parr(i * i : size(parr) : i) = .false.
end do
end subroutine
function is_rtp(candidate)
logical :: is_rtp
integer, intent(in) :: candidate
integer :: n
is_rtp = .true.
n = candidate / 10
do while(n > 0)
if(.not. primes(n)) then
is_rtp = .false.
return
end if
n = n / 10
end do
end function
function is_ltp(candidate)
logical :: is_ltp
integer, intent(in) :: candidate
integer :: i, n
character(10) :: nstr
write(nstr, "(i10)") candidate
is_ltp = .true.
do i = len_trim(nstr)-1, 1, -1
n = mod(candidate, 10**i)
if(.not. primes(n)) then
is_ltp = .false.
return
end if
end do
end function
end module primes_mod
program Truncatable_Primes
use primes_mod
implicit none
integer, parameter :: limit = 999999
integer :: i
character(10) :: nstr
! Generate an array of prime flags up to limit of search
allocate(primes(limit))
call Genprimes(primes)
! Find left truncatable prime
do i = limit, 1, -1
write(nstr, "(i10)") i
if(index(trim(nstr), "0") /= 0) cycle ! check for 0 in number
if(is_ltp(i)) then
write(*, "(a, i0)") "Largest left truncatable prime below 1000000 is ", i
exit
end if
end do
! Find right truncatable prime
do i = limit, 1, -1
write(nstr, "(i10)") i
if(index(trim(nstr), "0") /= 0) cycle ! check for 0 in number
if(is_rtp(i)) then
write(*, "(a, i0)") "Largest right truncatable prime below 1000000 is ", i
exit
end if
end do
end program</syntaxhighlight>
Output
<pre>Largest left truncatable prime below 1000000 is 998443
Largest right truncatable prime below 1000000 is 739399</pre>
=={{header|FreeBASIC}}==
===Version 1===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Function isPrime(n As Integer) As Boolean
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim d As Integer = 5
While d * d <= n
If n Mod d = 0 Then Return False
d += 2
If n Mod d = 0 Then Return False
d += 4
Wend
Return True
End Function
Dim As UInteger i, j, p, pow, lMax = 2, rMax = 2
Dim s As String
' largest left truncatable prime less than 1000000
' It can't end with 1, 4, 6, 8 or 9 as these numbers are not prime
' Nor can it end in 2 if it has more than one digit as such a number would divide by 2
For i = 3 To 999997 Step 2
s = Str(i)
If Instr(s, "0") > 1 Then Continue For '' cannot contain 0
j = s[Len(s) - 1] - 48
If j = 1 OrElse j = 9 Then Continue For
p = i
pow = 10 ^ (Len(s) - 1)
While pow > 1
If Not isPrime(p) Then Continue For
p Mod= pow
pow \= 10
Wend
lMax = i
Next
' largest right truncatable prime less than 1000000
' It can't begin with 1, 4, 6, 8 or 9 as these numbers are not prime
For i = 3 To 799999 Step 2
s = Str(i)
If Instr(s, "0") > 1 Then Continue For '' cannot contain 0
j = s[0] - 48
If j = 1 OrElse j = 4 OrElse j = 6 Then Continue For
p = i
While p > 0
If Not isPrime(p) Then Continue For
p \= 10
Wend
rMax = i
Next
Print "Largest left truncatable prime : "; lMax
Print "Largest right truncatable prime : "; rMax
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime : 998443
Largest right truncatable prime : 739399
</pre>
===Version 2===
Construct primes using previous found primes.
<syntaxhighlight lang="freebasic">' version 10-12-2016
' compile with: fbc -s console
Dim Shared As Byte isPrime()
Sub sieve(m As UInteger)
Dim As Integer i, j
ReDim isPrime(m)
For i = 4 To m Step 2
isPrime(i) = 1
Next
For i = 3 To Sqr(m) Step 2
If isPrime(i) = 0 Then
For j = i * i To m Step i * 2
isPrime(j) = 1
Next
End If
Next
End Sub
' ------=< MAIN >=------
#Define max 1000000 'upto 2^30 max for 32bit OS
Dim As UInteger a(), lt_prime(5000), rt_prime(100)
Dim As UInteger i, j, j1, p1, p2, left_max, right_max
sieve(max)
' left truncatable primes
' if odd and ends with 3 or 7, never ends 1 or 9 (no prime
' never ends on a 2 or 5 and starts with 1 to 9
lt_prime(1) = 3 : lt_prime(2) = 7
p1 = 1 : p2 = 2
Do
For i = 1 To 9
j = Val( Str(i) + Str(lt_prime(p1)) )
If j > max Then Exit Do
If isPrime(j) = 0 Then ' if prime then add to the list
p2 += 1
lt_prime(p2) = j
If Left_max < j Then left_max = j
End If
Next
p1 += 1
Loop Until p1 > p2 ' no more numbers to process
' right truncatable prime
' start with 2, 3, 5 or 7 and end with 1, 3, 7 or 9
rt_prime(1) = 2 : rt_prime(2) = 3 : rt_prime(3) = 5 : rt_prime(4) = 7
p1 = 1 : p2 = 4
Dim As UInteger end_num(1 To 4) => {1, 3, 7, 9}
Do
j1 = rt_prime(p1) * 10
If j1 > max Then Exit Do
For i = 1 To 4
j = j1 + End_num(i)
If isprime(j) = 0 Then ' if prime then add to the list
p2 += 1
rt_prime(p2) = j
' If right_max < j Then right_max = j
End If
Next
p1 += 1
Loop Until p1 > p2 ' no more numbers to process
' the last one added is the biggest
right_max = rt_prime(p2)
Print
Print "The biggest left truncatable prime below"; max; " is "; left_max
Print "The biggest right truncatable prime below"; max; " is "; right_max
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>
The biggest left truncatable prime below 1000000 is 998443
The biggest right truncatable prime below 1000000 is 739399</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
import "fmt"
func main() {
sieve(1e6)
if !search(6, 1e6, "left", func(n, pot int) int { return n % pot }) {
panic("997?")
}
if !search(6, 1e6, "right", func(n, _ int) int { return n / 10 }) {
panic("7393?")
}
}
var c []bool
func sieve(ss int) {
c = make([]bool, ss)
c[1] = true
for p := 2; ; {
p2 := p * p
if p2 >= ss {
break
}
for i := p2; i < ss; i += p {
c[i] = true
}
for {
p++
if !c[p] {
break
}
}
}
}
func search(digits, pot int, s string, truncFunc func(n, pot int) int) bool {
n := pot - 1
pot /= 10
smaller:
for ; n >= pot; n -= 2 {
for tn, tp := n, pot; tp > 0; tp /= 10 {
if tn < tp || c[tn] {
continue smaller
}
tn = truncFunc(tn, tp)
}
fmt.Println("max", s, "truncatable:", n)
return true
}
if digits > 1 {
return search(digits-1, pot, s, truncFunc)
}
return false
}</syntaxhighlight>
Output:
<pre>
max left truncatable: 998443
max right truncatable: 739399
</pre>
=={{header|Haskell}}==
Using {{libheader|Primes}} from [http://hackage.haskell.org/packages/hackage.html HackageDB]
<syntaxhighlight lang="haskell">import Data.Numbers.Primes(primes, isPrime)
import Data.List
import Control.Arrow
primes1e6 = reverse. filter (notElem '0'. show) $ takeWhile(<=1000000) primes
rightT, leftT :: Int -> Bool
rightT = all isPrime. takeWhile(>0). drop 1. iterate (`div`10)
leftT x = all isPrime. takeWhile(<x).map (x`mod`) $ iterate (*10) 10
main = do
let (ltp, rtp) = (head. filter leftT &&& head. filter rightT) primes1e6
putStrLn $ "Left truncatable " ++ show ltp
putStrLn $ "Right truncatable " ++ show rtp</syntaxhighlight>
Output:
<syntaxhighlight lang="haskell">*Main> main
Left truncatable 998443
Right truncatable 739399</syntaxhighlight>
Interpretation of the J contribution:
<syntaxhighlight lang="haskell">digits = [1..9] :: [Integer]
smallPrimes = filter isPrime digits
pow10 = iterate (*10) 1
mul10 = (pow10!!). length. show
righT = (+) . (10 *)
lefT = liftM2 (.) (+) ((*) . mul10)
primesTruncatable f = iterate (concatMap (filter isPrime.flip map digits. f)) smallPrimes</syntaxhighlight>
Output:
<syntaxhighlight lang="haskell">*Main> maximum $ primesTruncatable righT !! 5
739399
*Main> maximum $ primesTruncatable lefT !! 5
998443</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
<syntaxhighlight lang="icon">procedure main(arglist)
N := 0 < integer(\arglist[1]) | 1000000 # primes to generator 1 to ... (1M or 1st arglist)
D := (0 < integer(\arglist[2]) | 10) / 2 # primes to display (10 or 2nd arglist)
P := sieve(N) # from sieve task (modified)
write("There are ",*P," prime numbers in the range 1 to ",N)
if *P <= 2*D then
every writes( "Primes: "|!sort(P)||" "|"\n" )
else
every writes( "Primes: "|(L := sort(P))[1 to D]||" "|"... "|L[*L-D+1 to *L]||" "|"\n" )
largesttruncateable(P)
end
procedure largesttruncateable(P) #: find the largest left and right trucatable numbers in P
local ltp,rtp
every x := sort(P)[*P to 1 by -1] do # largest to smallest
if not find('0',x) then {
/ltp := islefttrunc(P,x)
/rtp := isrighttrunc(P,x)
if \ltp & \rtp then break # until both found
}
write("Largest left truncatable prime = ", ltp)
write("Largest right truncatable prime = ", rtp)
return
end
procedure isrighttrunc(P,x) #: return integer x if x and all right truncations of x are in P or fails
if x = 0 | (member(P,x) & isrighttrunc(P,x / 10)) then return x
end
procedure islefttrunc(P,x) #: return integer x if x and all left truncations of x are in P or fails
if *x = 0 | ( (x := integer(x)) & member(P,x) & islefttrunc(P,x[2:0]) ) then return x
end</syntaxhighlight>
Sample output:<pre>There are 78498 prime numbers in the range 1 to 1000000
Primes: 2 3 5 7 11 ... 999953 999959 999961 999979 999983
Largest left truncatable prime = 998443
Largest right truncatable prime = 739399</pre>
=={{header|J}}==
Truncatable primes may be constructed by starting with a set of one digit prime numbers and then repeatedly adding a non-zero digit (combine all possibilities of a truncatable prime digit sequence with each digit) and, at each step, selecting the prime numbers which result.
In other words, given:
<syntaxhighlight lang="j">selPrime=: #~ 1&p:
seed=: selPrime digits=: 1+i.9
step=: selPrime@,@:(,&.":/&>)@{@;</syntaxhighlight>
Here, selPrime discards non-prime numbers from a list, so seed is the list 2 3 5 7.
The largest truncatable primes less than a million can be obtained by adding five digits to the prime seeds, then finding the largest value from the result.
<syntaxhighlight lang="j"> >./ digits&step^:5 seed NB. left truncatable
998443
>./ step&digits^:5 seed NB. right truncatable
739399</syntaxhighlight>
Note that we are using the same combining function and same basic procedure in both cases. The difference is which side of the number we add arbitrary digits to, for each step.
=={{header|Java}}==
<syntaxhighlight lang="java">import java.util.BitSet;
public class Main {
public static void main(String[] args){
final int MAX = 1000000;
//Sieve of Eratosthenes (using BitSet only for odd numbers)
BitSet primeList = new BitSet(MAX>>1);
primeList.set(0,primeList.size(),true);
int sqroot = (int) Math.sqrt(MAX);
primeList.clear(0);
for(int num = 3; num <= sqroot; num+=2)
{
if( primeList.get(num >> 1) )
{
int inc = num << 1;
for(int factor = num * num; factor < MAX; factor += inc)
{
//if( ((factor) & 1) == 1)
//{
primeList.clear(factor >> 1);
//}
}
}
}
//Sieve ends...
//Find Largest Truncatable Prime. (so we start from 1000000 - 1
int rightTrunc = -1, leftTrunc = -1;
for(int prime = (MAX - 1) | 1; prime >= 3; prime -= 2)
{
if(primeList.get(prime>>1))
{
//Already found Right Truncatable Prime?
if(rightTrunc == -1)
{
int right = prime;
while(right > 0 && right % 2 != 0 && primeList.get(right >> 1)) right /= 10;
if(right == 0) rightTrunc = prime;
}
//Already found Left Truncatable Prime?
if(leftTrunc == -1 )
{
//Left Truncation
String left = Integer.toString(prime);
if(!left.contains("0"))
{
while( left.length() > 0 ){
int iLeft = Integer.parseInt(left);
if(!primeList.get( iLeft >> 1)) break;
left = left.substring(1);
}
if(left.length() == 0) leftTrunc = prime;
}
}
if(leftTrunc != -1 && rightTrunc != -1) //Found both? then Stop loop
{
break;
}
}
}
System.out.println("Left Truncatable : " + leftTrunc);
System.out.println("Right Truncatable : " + rightTrunc);
}
}
</syntaxhighlight>
Output :
<pre>
Left Truncatable : 998443
Right Truncatable : 739399
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
See [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime` as used here.
<syntaxhighlight lang="jq">def is_left_truncatable_prime:
def removeleft: recurse(if length <= 1 then empty else .[1:] end);
tostring
| index("0") == null and
all(removeleft|tonumber; is_prime);
def is_right_truncatable_prime:
def removeright: recurse(if length <= 1 then empty else .[:-1] end);
tostring
| index("0") == null and
all(removeright|tonumber; is_prime);
first( range(999999; 1; -2) | select(is_left_truncatable_prime)),
first( range(999999; 1; -2) | select(is_right_truncatable_prime))</syntaxhighlight>
{{out}}
<pre>
998443
739399
</pre>
=={{header|Julia}}==
There are several features of Julia that make solving this task easy. Julia has excellent built-in support for prime generation and testing. The built-in mathematical functions <tt>prevpow</tt> and <tt>divrem</tt> are quite handy for implementing <tt>isltruncprime</tt>.
<syntaxhighlight lang="julia">
function isltruncprime{T<:Integer}(n::T, base::T=10)
isprime(n) || return false
p = n
f = prevpow(base, p)
while 1 < f
(d, p) = divrem(p, f)
isprime(p) || return false
d != 0 || return false
f = div(f, base)
end
return true
end
function isrtruncprime{T<:Integer}(n::T, base::T=10)
isprime(n) || return false
p = n
while base < p
p = div(p, base)
isprime(p) || return false
end
return true
end
hi = 10^6
for i in reverse(primes(hi))
isltruncprime(i) || continue
println("The largest left truncatable prime ≤ ", hi, " is ", i, ".")
break
end
for i in reverse(primes(hi))
isrtruncprime(i) || continue
println("The largest right truncatable prime ≤ ", hi, " is ", i, ".")
break
end
</syntaxhighlight>
{{out}}
<pre>
The largest left truncatable prime ≤ 1000000 is 998443.
The largest right truncatable prime ≤ 1000000 is 739399.
</pre>
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="scala">// version 1.0.5-2
fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun main(args: Array<String>) {
var j: Char
var p: Int
var pow: Int
var lMax: Int = 2
var rMax: Int = 2
var s: String
// calculate maximum left truncatable prime less than 1 million
loop@ for( i in 3..999997 step 2) {
s = i.toString()
if ('0' in s) continue
j = s[s.length - 1]
if (j == '1' || j == '9') continue
p = i
pow = 1
for (k in 1..s.length - 1) pow *= 10
while(pow > 1) {
if (!isPrime(p)) continue@loop
p %= pow
pow /= 10
}
lMax = i
}
// calculate maximum right truncatable prime less than 1 million
loop@ for( i in 3..799999 step 2) {
s = i.toString()
if ('0' in s) continue
j = s[0]
if (j == '1' || j == '4' || j == '6') continue
p = i
while(p > 0) {
if (!isPrime(p)) continue@loop
p /= 10
}
rMax = i
}
println("Largest left truncatable prime : " + lMax.toString())
println("Largest right truncatable prime : " + rMax.toString())
}</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime : 998443
Largest right truncatable prime : 739399
</pre>
=={{header|Lua}}==
<syntaxhighlight lang="lua">max_number = 1000000
numbers = {}
for i = 2, max_number do
numbers[i] = i;
end
for i = 2, max_number do
for j = i+1, max_number do
if numbers[j] ~= 0 and j % i == 0 then numbers[j] = 0 end
end
end
max_prime_left, max_prime_right = 2, 2
for i = 2, max_number do
if numbers[i] ~= 0 then
local is_prime = true
local l = math.floor( i / 10 )
while l > 1 do
if numbers[l] == 0 then
is_prime = false
break
end
l = math.floor( l / 10 )
end
if is_prime then
max_prime_left = i
end
is_prime = true
local n = 10;
while math.floor( i % 10 ) ~= 0 and n < max_number do
if numbers[ math.floor( i % 10 ) ] ~= 0 then
is_prime = false
break
end
n = n * 10
end
if is_prime then
max_prime_right = i
end
end
end
print( "max_prime_left = ", max_prime_left )
print( "max_prime_right = ", max_prime_right )</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="maple">
MaxTruncatablePrime := proc({left::truefalse:=FAIL, right::truefalse:=FAIL}, $)
local i, j, c, p, b, n, sdprimes, dir;
local tprimes := table();
if left = true and right = true then
error "invalid input";
elif right = true then
dir := "right";
else
dir := "left";
end if;
b := 10;
n := 6;
sdprimes := select(isprime, [seq(1..b-1)]);
for p in sdprimes do
if assigned(tprimes[p]) then
next;
end if;
i := ilog[b](p)+1;
j := 1;
while p < b^n do
if dir = "left" then
c := j*b^i + p;
else
c := p*b + j;
end if;
if j >= b or c > b^n then # we have tried all 1 digit extensions of p, add p to tprimes and move back 1 digit
tprimes[p] := p;
if i = 1 then # if we are at the first digit, go to the next 1 digit prime
break;
end if;
i := i - 1;
j := 1;
if dir = "left" then
p := p - iquo(p, b^i)*b^i;
else
p := iquo(p, b);
end if;
elif assigned(tprimes[c]) then
j := j + 1;
elif isprime(c) then
p := c;
i := i + 1;
j := 1;
else
j := j+1;
end if;
end do;
end do;
return max(indices(tprimes, 'nolist'));
end proc;</syntaxhighlight>
<pre>
> MaxTruncatablePrime(right); MaxTruncatablePrime(left);
739399
998443
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">LeftTruncatablePrimeQ[n_] := Times @@ IntegerDigits[n] > 0 &&
And @@ PrimeQ /@ ToExpression /@ StringJoin /@
Rest[Most[NestList[Rest, #, Length[#]] &[Characters[ToString[n]]]]]
RightTruncatablePrimeQ[n_] := Times @@ IntegerDigits[n] > 0 &&
And @@ PrimeQ /@ ToExpression /@ StringJoin /@
Rest[Most[NestList[Most, #, Length[#]] &[Characters[ToString[n]]]]]</syntaxhighlight>
Example usage:
<pre>n = PrimePi[1000000]; While[Not[LeftTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]
-> 998443
n = PrimePi[1000000]; While[Not[RightTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]
-> 739399</pre>
=={{header|MATLAB}}==
largestTruncatablePrimes.m:
<syntaxhighlight lang="matlab">function largestTruncatablePrimes(boundary)
%Helper function for checking if a prime is left of right truncatable
function [leftTruncatable,rightTruncatable] = isTruncatable(prime,checkLeftTruncatable,checkRightTruncatable)
numDigits = ceil(log10(prime)); %calculate the number of digits in the prime less one
powersOfTen = 10.^(0:numDigits); %cache the needed powers of ten
leftTruncated = mod(prime,powersOfTen); %generate a list of numbers by repeatedly left truncating the prime
%leading zeros will cause duplicate entries thus it is possible to
%detect leading zeros if we rotate the list to the left or right
%and check for any equivalences with the original list
hasLeadingZeros = any( circshift(leftTruncated,[0 1]) == leftTruncated );
if( hasLeadingZeros || not(checkLeftTruncatable) )
leftTruncatable = false;
else
%check if all of the left truncated numbers are prime
leftTruncatable = all(isprime(leftTruncated(2:end)));
end
if( checkRightTruncatable )
rightTruncated = (prime - leftTruncated) ./ powersOfTen; %generate a list of right truncated numbers
rightTruncatable = all(isprime(rightTruncated(1:end-1))); %check if all the right truncated numbers are prime
else
rightTruncatable = false;
end
end %isTruncatable()
nums = primes(boundary); %generate all primes <= boundary
%Flags that indicate if the largest left or right truncatable prime has not
%been found
leftTruncateNotFound = true;
rightTruncateNotFound = true;
for prime = nums(end:-1:1) %Search through primes in reverse order
%Get if the prime is left and/or right truncatable, ignoring
%checking for right truncatable if it has already been found
[leftTruncatable,rightTruncatable] = isTruncatable(prime,leftTruncateNotFound,rightTruncateNotFound);
if( leftTruncateNotFound && leftTruncatable ) %print out largest left truncatable prime
display([num2str(prime) ' is the largest left truncatable prime <= ' num2str(boundary) '.']);
leftTruncateNotFound = false;
end
if( rightTruncateNotFound && rightTruncatable ) %print out largest right truncatable prime
display([num2str(prime) ' is the largest right truncatable prime <= ' num2str(boundary) '.']);
rightTruncateNotFound = false;
end
%Terminate loop when the largest left and right truncatable primes have
%been found
if( not(leftTruncateNotFound || rightTruncateNotFound) )
break;
end
end
end
</syntaxhighlight>
Solution for n = 1,000,000:
<syntaxhighlight lang="matlab">
>> largestTruncatablePrimes(1e6)
998443 is the largest left truncatable prime <= 1000000.
739399 is the largest right truncatable prime <= 1000000.
</syntaxhighlight>
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="nim">import sets, strutils, algorithm
proc primes(n: int64): seq[int64] =
var multiples: HashSet[int64]
for i in 2..n:
if i notin multiples:
result.add i
for j in countup(i*i, n, i.int):
multiples.incl j
proc truncatablePrime(n: int64): tuple[left, right: int64] =
var
primelist: seq[string]
for x in primes(n):
primelist.add($x)
reverse primelist
var primeset = primelist.toHashSet
for n in primelist:
var alltruncs: HashSet[string]
for i in 0..n.high:
alltruncs.incl n[i..n.high]
if alltruncs <= primeset:
result.left = parseInt(n)
break
for n in primelist:
var alltruncs: HashSet[string]
for i in 0..n.high:
alltruncs.incl n[0..i]
if alltruncs <= primeset:
result.right = parseInt(n)
break
echo truncatablePrime(1000000i64)</syntaxhighlight>
{{out}}
<pre>(left: 998443, right: 739399)</pre>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
-- find largest left- & right-truncatable primes < 1 million.
-- an initial set of primes (not, at this time, we leave out 2 because
-- we'll automatically skip the even numbers. No point in doing a needless
-- test each time through
primes = .array~of(3, 5, 7, 11)
-- check all of the odd numbers up to 1,000,000
loop j = 13 by 2 to 1000000
loop i = 1 to primes~size
prime = primes[i]
-- found an even prime divisor
if j // prime == 0 then iterate j
-- only check up to the square root
if prime*prime > j then leave
end
-- we only get here if we don't find a divisor
primes~append(j)
end
-- get a set of the primes that we can test more efficiently
primeSet = .set~of(2)
primeSet~putall(primes)
say 'The last prime is' primes[primes~last] "("primeSet~items 'primes under one million).'
say copies('-',66)
lastLeft = 0
-- we're going to use the array version to do these in order. We're still
-- missing "2", but that's not going to be the largest
loop prime over primes
-- values containing 0 can never work
if prime~pos(0) \= 0 then iterate
-- now start the truncations, checking against our set of
-- known primes
loop i = 1 for prime~length - 1
subprime = prime~right(i)
-- not in our known set, this can't work
if \primeset~hasIndex(subprime) then iterate prime
end
-- this, by definition, with be the largest left-trunc prime
lastLeft = prime
end
-- now look for right-trunc primes
lastRight = 0
loop prime over primes
-- values containing 0 can never work
if prime~pos(0) \= 0 then iterate
-- now start the truncations, checking against our set of
-- known primes
loop i = 1 for prime~length - 1
subprime = prime~left(i)
-- not in our known set, this can't work
if \primeset~hasIndex(subprime) then iterate prime
end
-- this, by definition, with be the largest left-trunc prime
lastRight = prime
end
say 'The largest left-truncatable prime is' lastLeft '(under one million).'
say 'The largest right-truncatable prime is' lastRight '(under one million).'
</syntaxhighlight>
Output:
<pre>
The last prime is 999983 (78498 primes under one million).
------------------------------------------------------------------
The largest left-truncatable prime is 998443 (under one million).
The largest right-truncatable prime is 739399 (under one million).
</pre>
=={{header|OpenEdge/Progress}}==
<syntaxhighlight lang="progress">FUNCTION isPrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT.
DO ii = 2 TO SQRT( i_i ):
IF i_i MODULO ii = 0 THEN
RETURN FALSE.
END.
RETURN TRUE AND i_i > 1.
END FUNCTION. /* isPrime */
FUNCTION isLeftTruncatablePrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT.
DEF VAR cc AS CHAR.
DEF VAR lresult AS LOGICAL INITIAL TRUE.
cc = STRING( i_i ).
DO WHILE cc > "":
lresult = lresult AND isPrime( INTEGER( cc ) ).
cc = SUBSTRING( cc, 2 ).
END.
RETURN lresult.
END FUNCTION. /* isLeftTruncatablePrime */
FUNCTION isRightTruncatablePrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT.
DEF VAR cc AS CHAR.
DEF VAR lresult AS LOGICAL INITIAL TRUE.
cc = STRING( i_i ).
DO WHILE cc > "":
lresult = lresult AND isPrime( INTEGER( cc ) ).
cc = SUBSTRING( cc, 1, LENGTH( cc ) - 1 ).
END.
RETURN lresult.
END FUNCTION. /* isRightTruncatablePrime */
FUNCTION getHighestTruncatablePrimes RETURNS CHARACTER (
i_imax AS INTEGER
):
DEF VAR ii AS INT.
DEF VAR ileft AS INT.
DEF VAR iright AS INT.
DO ii = i_imax TO 1 BY -1 WHILE ileft = 0 OR iright = 0:
IF INDEX( STRING( ii ), "0" ) = 0 THEN DO:
IF ileft = 0 AND isLeftTruncatablePrime( ii ) THEN
ileft = ii.
IF iright = 0 AND isRightTruncatablePrime( ii ) THEN
iright = ii.
END.
END.
RETURN SUBSTITUTE("Left: &1~nRight: &2", ileft, iright ).
END FUNCTION. /* getHighestTruncatablePrimes */
MESSAGE
getHighestTruncatablePrimes( 1000000 )
VIEW-AS ALERT-BOX.
</syntaxhighlight>
Output:
<pre>---------------------------
Message
---------------------------
Left: 998443
Right: 739399
---------------------------
OK
---------------------------</pre>
=={{header|PARI/GP}}==
This version builds the truncatable primes with up to k digits in a straightforward fashion. Run time is about 15 milliseconds, almost all of which is I/O.
<syntaxhighlight lang="parigp">left(n)={
my(v=[2,3,5,7],u,t=1,out=0);
for(i=1,n,
t*=10;
u=[];
for(j=1,#v,
forstep(a=t,t*9,t,
if(isprime(a+v[j]),u=concat(u,a+v[j]))
)
);
out=v[#v];
v=vecsort(u)
);
out
};
right(n)={
my(v=[2,3,5,7],u,out=0);
for(i=1,n,
u=[];
for(j=1,#v,
forstep(a=1,9,[2,4],
if(isprime(10*v[j]+a),u=concat(u,10*v[j]+a))
)
);
out=v[#v];
v=u
);
out
};
[left(6),right(6)]</syntaxhighlight>
=={{header|Perl}}==
Typically with Perl we'll look for a CPAN module to make our life easier. This basically just follows the task rules:
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use ntheory ":all";
sub isltrunc {
my $n = shift;
return (is_prime($n) && $n !~ /0/ && ($n < 10 || isltrunc(substr($n,1))));
}
sub isrtrunc {
my $n = shift;
return (is_prime($n) && $n !~ /0/ && ($n < 10 || isrtrunc(substr($n,0,-1))));
}
for (reverse @{primes(1e6)}) {
if (isltrunc($_)) { print "ltrunc: $_\n"; last; }
}
for (reverse @{primes(1e6)}) {
if (isrtrunc($_)) { print "rtrunc: $_\n"; last; }
}</syntaxhighlight>
{{out}}
<pre>ltrunc: 998443
rtrunc: 739399</pre>
We can be a little more Perlish and build up n-digit lists then select the last one:
<syntaxhighlight lang="perl">use ntheory ":all";
my @lprimes = my @rprimes = (2,3,5,7);
@lprimes = sort { $a <=> $b }
map { my $p=$_; map { is_prime($_.$p) ? $_.$p : () } 1..9 } @lprimes
for 2..6;
@rprimes = sort { $a <=> $b }
map { my $p=$_; map { is_prime($p.$_) ? $p.$_ : () } 1..9 } @rprimes
for 2..6;
print "ltrunc: $lprimes[-1]\nrtrunc: $rprimes[-1]\n";</syntaxhighlight>
Or we can do everything ourselves:
<syntaxhighlight lang="perl">#!/usr/bin/perl
use warnings;
use strict;
use constant {
LEFT => 0,
RIGHT => 1,
};
{ my @primes = (2, 3);
sub is_prime {
my $n = shift;
return if $n < 2;
for my $prime (@primes) {
last if $prime >= $n;
return unless $n % $prime;
}
my $sqrt = sqrt $n;
while ($primes[-1] < $sqrt) {
my $new = 2 + $primes[-1];
$new += 2 until is_prime($new);
push @primes, $new;
return unless $n % $new;
}
return 1;
}
}
sub trunc {
my ($n, $side) = @_;
substr $n, $side == LEFT ? 0 : -1, 1, q();
return $n;
}
sub is_tprime { # Absence of zeroes is tested outside the sub.
my ($n, $side) = @_;
return (is_prime($n)
and (1 == length $n or is_tprime(trunc($n, $side), $side)));
}
my $length = 6;
my @tprimes = ('9' x $length) x 2;
for my $side (LEFT, RIGHT) {
$tprimes[$side] -= 2 until -1 == index $tprimes[$side], '0'
and is_tprime($tprimes[$side], $side);
}
print 'left ', join(', right ', @tprimes), "\n";</syntaxhighlight>
{{out}}
<pre>left 998443, right 739399</pre>
=={{header|Phix}}==
A slightly different approach. Works up to N=8, quite fast - 10^8 in 5s with ~90% of time spent creating the basic sieve and ~10% propagation and final scan.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- standard sieve:</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">L</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span> <span style="color: #000080;font-style:italic;">-- (with primes[i] as mini bit-field)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">L</span><span style="color: #0000FF;">+</span><span style="color: #000000;">R</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- propagate non-truncateables up the prime table:</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p10</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ie 10, 100, .. 100_000</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">p10</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- to 99, 999, .. 999_999</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">],</span><span style="color: #000000;">L</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">],</span><span style="color: #000000;">R</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">L</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">maxl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">maxr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">maxl</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxr</span><span style="color: #0000FF;">}</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
{998443,739399}
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(load "@lib/rsa.l") # Use the 'prime?' function from RSA package
(de truncatablePrime? (N Fun)
(for (L (chop N) L (Fun L))
(T (= "0" (car L)))
(NIL (prime? (format L)))
T ) )
(let (Left 1000000 Right 1000000)
(until (truncatablePrime? (dec 'Left) cdr))
(until (truncatablePrime? (dec 'Right) '((L) (cdr (rot L)))))
(cons Left Right) )</syntaxhighlight>
Output:
<pre>-> (998443 . 739399)</pre>
=={{header|Pike}}==
<syntaxhighlight lang="pike">bool is_trunc_prime(int p, string direction)
{
while(p) {
if( !p->probably_prime_p() )
return false;
if(direction == "l")
p = (int)p->digits()[1..];
else
p = (int)p->digits()[..<1];
}
return true;
}
void main()
{
bool ltp_found, rtp_found;
for(int prime = 10->pow(6); prime--; prime > 0) {
if( !ltp_found && is_trunc_prime(prime, "l") ) {
ltp_found = true;
write("Largest LTP: %d\n", prime);
}
if( !rtp_found && is_trunc_prime(prime, "r") ) {
rtp_found = true;
write("Largest RTP: %d\n", prime);
}
if(ltp_found && rtp_found)
break;
}
}</syntaxhighlight>
Output:
<pre>
Largest LTP: 999907
Largest RTP: 739399
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
tp: procedure options (main);
declare primes(1000000) bit (1);
declare max_primes fixed binary (31);
declare (i, k) fixed binary (31);
max_primes = hbound(primes, 1);
call sieve;
/* Now search for primes that are right-truncatable. */
call right_truncatable;
/* Now search for primes that are left-truncatable. */
call left_truncatable;
right_truncatable: procedure;
declare direction bit (1);
declare (i, k) fixed binary (31);
test_truncatable:
do i = max_primes to 2 by -1;
if primes(i) then /* it's a prime */
do;
k = i/10;
do while (k > 0);
if ^primes(k) then iterate test_truncatable;
k = k/10;
end;
put skip list (i || ' is right-truncatable');
return;
end;
end;
end right_truncatable;
left_truncatable: procedure;
declare direction bit (1);
declare (i, k, d, e) fixed binary (31);
test_truncatable:
do i = max_primes to 2 by -1;
if primes(i) then /* it's a prime */
do;
k = i;
do d = 100000 repeat d/10 until (d = 10);
e = k/d;
k = k - e*d;
if e = 0 then iterate test_truncatable;
if ^primes(k) then iterate test_truncatable;
end;
put skip list (i || ' is left-truncatable');
return;
end;
end;
end left_truncatable;
sieve: procedure;
declare (i, j) fixed binary (31);
primes = '1'b; primes(1) = '0'b;
do i = 2 to sqrt(max_primes);
do j = i+i to max_primes by i;
primes(j) = '0'b;
end;
end;
end sieve;
end tp;
</syntaxhighlight>
<pre>
739399 is right-truncatable
998443 is left-truncatable
</pre>
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">function IsPrime ( [int] $num )
{
$isprime = @{}
2..[math]::sqrt($num) | Where-Object {
$isprime[$_] -eq $null } | ForEach-Object {
$_
$isprime[$_] = $true
for ( $i=$_*$_ ; $i -le $num; $i += $_ )
{ $isprime[$i] = $false }
}
2..$num | Where-Object { $isprime[$_] -eq $null }
}
function Truncatable ( [int] $num )
{
$declen = [math]::abs($num).ToString().Length
$primes = @()
$ltprimes = @{}
$rtprimes = @{}
1..$declen | ForEach-Object { $ltprimes[$_]=@{}; $rtprimes[$_]=@{} }
IsPrime $num | ForEach-Object {
$lastltprime = 2
$lastrtprime = 2
} {
$curprim = $_
$curdeclen = $curprim.ToString().Length
$primes += $curprim
if( $curdeclen -eq 1 ) {
$ltprimes[1][$curprim] = $true
$rtprimes[1][$curprim] = $true
$lastltprime = $curprim
$lastrtprime = $curprim
} else {
$curmod = $curprim % [math]::pow(10,$curdeclen - 1)
$curdiv = [math]::floor($curprim / 10)
if( $ltprimes[$curdeclen - 1][[int]$curmod] ) {
$ltprimes[$curdeclen][$curprim] = $true
$lastltprime = $curprim
}
if( $rtprimes[$curdeclen - 1][[int]$curdiv] ) {
$rtprimes[$curdeclen][$curprim] = $true
$lastrtprime = $curprim
}
}
if( ( $ltprimes[$curdeclen - 2].Keys.count -gt 0 ) -and ( $ltprimes[$curdeclen - 1].Keys.count -gt 0 ) ) { $ltprimes[$curdeclen -2] = @{} }
if( ( $rtprimes[$curdeclen - 2].Keys.count -gt 0 ) -and ( $rtprimes[$curdeclen - 1].Keys.count -gt 0 ) ) { $rtprimes[$curdeclen -2] = @{} }
} {
"Largest Left Truncatable Prime: $lastltprime"
"Largest Right Truncatable Prime: $lastrtprime"
}
}</syntaxhighlight>
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<syntaxhighlight lang="prolog">largest_left_truncatable_prime(N, N):-
is_left_truncatable_prime(N),
!.
largest_left_truncatable_prime(N, P):-
N > 1,
N1 is N - 1,
largest_left_truncatable_prime(N1, P).
is_left_truncatable_prime(P):-
is_prime(P),
is_left_truncatable_prime(P, P, 10).
is_left_truncatable_prime(P, _, N):-
P =< N,
!.
is_left_truncatable_prime(P, Q, N):-
Q1 is P mod N,
is_prime(Q1),
Q \= Q1,
N1 is N * 10,
is_left_truncatable_prime(P, Q1, N1).
largest_right_truncatable_prime(N, N):-
is_right_truncatable_prime(N),
!.
largest_right_truncatable_prime(N, P):-
N > 1,
N1 is N - 1,
largest_right_truncatable_prime(N1, P).
is_right_truncatable_prime(P):-
is_prime(P),
Q is P // 10,
(Q == 0, ! ; is_right_truncatable_prime(Q)).
main(N):-
find_prime_numbers(N),
largest_left_truncatable_prime(N, L),
writef('Largest left-truncatable prime less than %t: %t\n', [N, L]),
largest_right_truncatable_prime(N, R),
writef('Largest right-truncatable prime less than %t: %t\n', [N, R]).
main:-
main(1000000).</syntaxhighlight>
Module for finding prime numbers up to some limit:
<syntaxhighlight lang="prolog">:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
find_prime_numbers(N):-
retractall(is_prime(_)),
assertz(is_prime(2)),
init_sieve(N, 3),
sieve(N, 3).
init_sieve(N, P):-
P > N,
!.
init_sieve(N, P):-
assertz(is_prime(P)),
Q is P + 2,
init_sieve(N, Q).
sieve(N, P):-
P * P > N,
!.
sieve(N, P):-
is_prime(P),
!,
S is P * P,
cross_out(S, N, P),
Q is P + 2,
sieve(N, Q).
sieve(N, P):-
Q is P + 2,
sieve(N, Q).
cross_out(S, N, _):-
S > N,
!.
cross_out(S, N, P):-
retract(is_prime(S)),
!,
Q is S + 2 * P,
cross_out(Q, N, P).
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</syntaxhighlight>
{{out}}
<pre>
Largest left-truncatable prime less than 1000000: 998443
Largest right-truncatable prime less than 1000000: 739399
</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">#MaxLim = 999999
Procedure is_Prime(n)
If n<=1 : ProcedureReturn #False
ElseIf n<4 : ProcedureReturn #True
ElseIf n%2=0: ProcedureReturn #False
ElseIf n<9 : ProcedureReturn #True
ElseIf n%3=0: ProcedureReturn #False
Else
Protected r=Round(Sqr(n),#PB_Round_Down)
Protected f=5
While f<=r
If n%f=0 Or n%(f+2)=0
ProcedureReturn #False
EndIf
f+6
Wend
EndIf
ProcedureReturn #True
EndProcedure
Procedure TruncateLeft(n)
Protected s.s=Str(n), l=Len(s)-1
If Not FindString(s,"0",1)
While l>0
s=Right(s,l)
If Not is_Prime(Val(s))
ProcedureReturn #False
EndIf
l-1
Wend
ProcedureReturn #True
EndIf
EndProcedure
Procedure TruncateRight(a)
Repeat
a/10
If Not a
Break
ElseIf Not is_Prime(a) Or a%10=0
ProcedureReturn #False
EndIf
ForEver
ProcedureReturn #True
EndProcedure
i=#MaxLim
Repeat
If is_Prime(i)
If Not truncateleft And TruncateLeft(i)
truncateleft=i
EndIf
If Not truncateright And TruncateRight(i)
truncateright=i
EndIf
EndIf
If truncateleft And truncateright
Break
Else
i-2
EndIf
Until i<=0
x.s="Largest TruncateLeft= "+Str(truncateleft)
y.s="Largest TruncateRight= "+Str(truncateright)
MessageRequester("Truncatable primes",x+#CRLF$+y)</syntaxhighlight>
=={{header|Python}}==
<syntaxhighlight lang="python">maxprime = 1000000
def primes(n):
Line 23 ⟶ 3,097:
primeset = set(primelist)
for n in primelist:
# n = 'abc'; [n[i:] for i in range(len(n))] -> ['abc', 'bc', 'c']
alltruncs = set(n[i:] for i in range(len(n)))
if alltruncs.issubset(primeset):
Line 28 ⟶ 3,103:
break
for n in primelist:
# n = 'abc'; [n[:i+1] for i in range(len(n))] -> ['a', 'ab', 'abc']
alltruncs = set([n[:i+1] for i in range(len(n))])
if alltruncs.issubset(primeset):
Line 34 ⟶ 3,110:
return truncateleft, truncateright
print(truncatableprime(maxprime))</
'''Sample Output'''
<pre>(998443, 739399)</pre>
=={{header|Quackery}}==
<code>eratosthenes</code> and <code>sieve</code> are defined at [[Sieve of Eratosthenes#Quackery]].
<syntaxhighlight lang="quackery"> 1000000 eratosthenes
[ false swap
number$ witheach
[ char 0 =
if [ conclude not ] ] ] is haszero ( n --> b )
[ 10 / ] is truncright ( n --> n )
[ number$
behead drop $->n drop ] is truncleft ( n --> n )
[ dup isprime not iff
[ drop false ] done
dup haszero iff
[ drop false ] done
true swap
[ truncleft
dup 0 > while
dup isprime not iff
[ dip not ] done
again ] drop ] is ltruncatable ( n --> b )
[ dup isprime not iff
[ drop false ] done
dup haszero iff
[ drop false ] done
true swap
[ truncright
dup 0 > while
dup isprime not iff
[ dip not ] done
again ] drop ] is rtruncatable ( n --> b )
say "Left: "
1000000 times [ i ltruncatable if [ i echo conclude ] ]
cr
say "Right: "
1000000 times [ i rtruncatable if [ i echo conclude ] ]
cr</syntaxhighlight>
{{out}}
<pre>Left: 998443
Right: 739399
</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(require math/number-theory)
(define (truncate-right n)
(quotient n 10))
(define (truncate-left n)
(define s (number->string n))
(string->number (substring s 1 (string-length s))))
(define (contains-zero? n)
(member #\0 (string->list (number->string n))))
(define (truncatable? truncate n)
(and (prime? n)
(not (contains-zero? n))
(or (< n 10)
(truncatable? truncate (truncate n)))))
; largest left truncatable prime
(for/first ([n (in-range 1000000 1 -1)]
#:when (truncatable? truncate-left n))
n)
; largest right truncatable prime
(for/first ([n (in-range 1000000 1 -1)]
#:when (truncatable? truncate-right n))
n)
; Output:
998443
739399
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2015.09}}
<syntaxhighlight lang="raku" line>constant ltp = $[2, 3, 5, 7], -> @ltp {
$[ grep { .&is-prime }, ((1..9) X~ @ltp) ]
} ... *;
constant rtp = $[2, 3, 5, 7], -> @rtp {
$[ grep { .&is-prime }, (@rtp X~ (1..9)) ]
} ... *;
say "Highest ltp = ", ltp[5][*-1];
say "Highest rtp = ", rtp[5][*-1];</syntaxhighlight>
{{out}}
<pre>Highest ltp: 998443
Highest rtp: 739399</pre>
=={{header|REXX}}==
Extra code was added to the prime number generator as this is the section of the REXX program that consumes the vast majority of the computation time.
<syntaxhighlight lang="rexx">/*REXX program finds largest left─ and right─truncatable primes ≤ 1m (or argument 1).*/
parse arg hi .; if hi=='' then hi= 1000000 /*Not specified? Then use default of 1m*/
call genP /*generate some primes, about hi ÷ 2 */
/* [↓] find largest left truncatable P*/
do L=# by -1 for # /*search from top end; get the length.*/
do k=1 for length(@.L); _= right(@.L, k) /*validate all left truncatable primes.*/
if \!._ then iterate L /*Truncated number not prime? Skip it.*/
end /*k*/
leave /*egress, found left truncatable prime.*/
end /*L*/
/* [↓] find largest right truncated P.*/
do R=# by -1 for # /*search from top end; get the length.*/
do k=1 for length(@.R); _= left(@.R, k) /*validate all right truncatable primes*/
if \!._ then iterate R /*Truncated number not prime? Skip it.*/
end /*k*/
leave /*egress, found right truncatable prime*/
end /*R*/
say 'The largest left─truncatable prime ≤' hi " is " right(@.L, w)
say 'The largest right─truncatable prime ≤' hi " is " right(@.R, w)
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: !.= 0; w= length(hi) /*placeholders for primes; max width. */
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 for max(0, hi%2-@.#%2-1) /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above five lines saves time*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/
return</syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
The largest left─truncatable prime ≤ 1000000 is 998443
The largest right─truncatable prime ≤ 1000000 is 739399
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Truncatable primes
for n = 1000000 to 1 step -1
flag = 1
flag2 = 1
strn = string(n)
for nr = 1 to len(strn)
if strn[nr] = "0"
flag2 = 0
ok
next
if flag2 = 1
for m = 1 to len(strn)
strp = right(strn, m)
if isprime(number(strp))
else
flag = 0
exit
ok
next
if flag = 1
nend = n
exit
ok
ok
next
see "Largest left truncatable prime : " + nend + nl
for n = 1000000 to 1 step -1
flag = 1
strn = string(n)
for m = 1 to len(strn)
strp = left(strn, len(strn) - m + 1)
if isprime(number(strp))
else
flag = 0
exit
ok
next
if flag = 1
nend = n
exit
ok
next
see "Largest right truncatable prime : " + nend + nl
func isprime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
</syntaxhighlight>
Output:
<pre>
Largest left truncatable prime : 998443
Largest right truncatable prime : 739399
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ → trunc
≪ <span style="color:red">1000000</span>
'''DO'''
'''DO''' PREVPRIME '''UNTIL''' DUP →STR <span style="color:red">"0"</span> POS NOT '''END'''
DUP <span style="color:red">1</span> SF
'''DO'''
trunc EVAL
'''IF''' DUP ISPRIME? NOT '''THEN''' <span style="color:red">1</span> CF '''END'''
'''UNTIL''' DUP <span style="color:red">9</span> ≤ <span style="color:red">1</span> FC? OR '''END'''
DROP
'''UNTIL''' <span style="color:red">1</span> FS? '''END'''
≫ ≫ '<span style="color:blue">XTRUNC</span>' STO
≪ →STR TAIL STR→ ≫ <span style="color:blue">XTRUNC</span>
≪ <span style="color:red">10</span> / IP ≫ <span style="color:blue">XTRUNC</span>
{{out}}
<pre>
2: 998443
1: 739399
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def left_truncatable?(n)
truncatable?(n) {|i| i.to_s[1..-1].to_i}
end
def right_truncatable?(n)
truncatable?(n) {|i| i/10}
end
def truncatable?(n, &trunc_func)
return false if n.to_s.include? "0"
loop do
n = trunc_func.call(n)
return true if n.zero?
return false unless Prime.prime?(n)
end
end
require 'prime'
primes = Prime.each(1_000_000).to_a.reverse
p primes.detect {|p| left_truncatable? p}
p primes.detect {|p| right_truncatable? p}</syntaxhighlight>
returns
<pre>998443
739399</pre>
===An Alternative Approach===
Setting BASE to 10 and MAX to 6 in the Ruby example [[Find largest left truncatable prime in a given base|here]] Produces:
<pre>
The largest left truncatable prime less than 1000000 in base 10 is 998443
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn is_prime(n: u32) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
if n % 3 == 0 {
return n == 3;
}
let mut p = 5;
while p * p <= n {
if n % p == 0 {
return false;
}
p += 2;
if n % p == 0 {
return false;
}
p += 4;
}
true
}
fn is_left_truncatable(p: u32) -> bool {
let mut n = 10;
let mut q = p;
while p > n {
if !is_prime(p % n) || q == p % n {
return false;
}
q = p % n;
n *= 10;
}
true
}
fn is_right_truncatable(p: u32) -> bool {
let mut q = p / 10;
while q > 0 {
if !is_prime(q) {
return false;
}
q /= 10;
}
true
}
fn main() {
let limit = 1000000;
let mut largest_left = 0;
let mut largest_right = 0;
let mut p = limit;
while p >= 2 {
if is_prime(p) && is_left_truncatable(p) {
largest_left = p;
break;
}
p -= 1;
}
println!("Largest left truncatable prime is {}", largest_left);
p = limit;
while p >= 2 {
if is_prime(p) && is_right_truncatable(p) {
largest_right = p;
break;
}
p -= 1;
}
println!("Largest right truncatable prime is {}", largest_right);
}</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Scala}}==
This example uses lazily evaluated lists. The functions to determine if a number is a truncatable prime construct a list of truncated numbers and check that all the elements in the list are prime.
<syntaxhighlight lang="scala">object TruncatablePrimes {
def main(args: Array[String]): Unit = {
val max = 1000000
println(
s"""|ltPrime: ${ltPrimes.takeWhile(_ <= max).last}
|rtPrime: ${rtPrimes.takeWhile(_ <= max).last}
|""".stripMargin)
}
def ltPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isLeftTruncPrime)
def rtPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isRightTruncPrime)
def isPrime(num: Int): Boolean = (num > 1) && !LazyList.range(3, math.sqrt(num).toInt + 1, 2).exists(num%_ == 0)
def isLeftTruncPrime(num: Int): Boolean = !num.toString.contains('0') && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.tail)) else None}.forall(isPrime)
def isRightTruncPrime(num: Int): Boolean = !num.toString.exists(_.asDigit%2 == 0) && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.init)) else None}.forall(isPrime)
}</syntaxhighlight>
{{out}}
<pre>ltPrime: 998443
rtPrime: 739399</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func t_prime(n, left=true) {
var p = %w(2 3 5 7);
var f = (
left ? { '1'..'9' ~X+ p }
: { p ~X+ '1'..'9' }
)
n.times {
p = f().grep{ .to_i.is_prime }
}
p.map{.to_i}.max
}
say t_prime(5, left: true)
say t_prime(5, left: false)</syntaxhighlight>
{{out}}
<pre>
998443
739399
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">func isPrime(_ n: Int) -> Bool {
if n < 2 {
return false
}
if n % 2 == 0 {
return n == 2
}
if n % 3 == 0 {
return n == 3
}
var p = 5
while p * p <= n {
if n % p == 0 {
return false
}
p += 2
if n % p == 0 {
return false
}
p += 4
}
return true
}
func isLeftTruncatable(_ p: Int) -> Bool {
var n = 10
var q = p
while p > n {
if !isPrime(p % n) || q == p % n {
return false
}
q = p % n
n *= 10
}
return true
}
func isRightTruncatable(_ p: Int) -> Bool {
var q = p / 10
while q > 0 {
if !isPrime(q) {
return false
}
q /= 10
}
return true
}
let limit = 1000000
var largestLeft = 0
var largestRight = 0
var p = limit
while p >= 2 {
if isPrime(p) && isLeftTruncatable(p) {
largestLeft = p
break
}
p -= 1
}
print("Largest left truncatable prime is \(largestLeft)")
p = limit
while p >= 2 {
if isPrime(p) && isRightTruncatable(p) {
largestRight = p
break
}
p -= 1
}
print("Largest right truncatable prime is \(largestRight)")</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Tcl}}==
<syntaxhighlight lang="tcl">package require Tcl 8.5
# Optimized version of the Sieve-of-Eratosthenes task solution
proc sieve n {
set primes [list]
if {$n < 2} {return $primes}
set nums [dict create]
for {set i 2} {$i <= $n} {incr i} {
dict set nums $i ""
}
set next 2
set limit [expr {sqrt($n)}]
while {$next <= $limit} {
for {set i $next} {$i <= $n} {incr i $next} {dict unset nums $i}
lappend primes $next
dict for {next -} $nums break
}
return [concat $primes [dict keys $nums]]
}
proc isLeftTruncatable n {
global isPrime
while {[string length $n] > 0} {
if {![info exist isPrime($n)]} {
return false
}
set n [string range $n 1 end]
}
return true
}
proc isRightTruncatable n {
global isPrime
while {[string length $n] > 0} {
if {![info exist isPrime($n)]} {
return false
}
set n [string range $n 0 end-1]
}
return true
}
# Demo code
set limit 1000000
puts "calculating primes up to $limit"
set primes [sieve $limit]
puts "search space contains [llength $primes] members"
foreach p $primes {
set isPrime($p) "yes"
}
set primes [lreverse $primes]
puts "searching for largest left-truncatable prime"
foreach p $primes {
if {[isLeftTruncatable $p]} {
puts FOUND:$p
break
}
}
puts "searching for largest right-truncatable prime"
foreach p $primes {
if {[isRightTruncatable $p]} {
puts FOUND:$p
break
}
}</syntaxhighlight>
Output:
<pre>
calculating primes up to 1000000
search space contains 78498 members
searching for largest left-truncatable prime
FOUND:998443
searching for largest right-truncatable prime
FOUND:739399
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
start_time = Now
lt = 0
rt = 0
For h = 1 To 1000000
If IsLeftTruncatable(h) And h > lt Then
lt = h
End If
If IsRightTruncatable(h) And h > rt Then
rt = h
End If
Next
end_time = now
WScript.StdOut.WriteLine "Largest LTP from 1..1000000: " & lt
WScript.StdOut.WriteLine "Largest RTP from 1..1000000: " & rt
WScript.StdOut.WriteLine "Elapse Time(seconds) : " & DateDiff("s",start_time,end_time)
'------------
Function IsLeftTruncatable(n)
IsLeftTruncatable = False
c = 0
For i = Len(n) To 1 Step -1
If InStr(1,n,"0") > 0 Then
Exit For
End If
If IsPrime(Right(n,i)) Then
c = c + 1
End If
Next
If c = Len(n) Then
IsLeftTruncatable = True
End If
End Function
Function IsRightTruncatable(n)
IsRightTruncatable = False
c = 0
For i = Len(n) To 1 Step -1
If InStr(1,n,"0") > 0 Then
Exit For
End If
If IsPrime(Left(n,i)) Then
c = c + 1
End If
Next
If c = Len(n) Then
IsRightTruncatable = True
End If
End Function
Function IsPrime(n)
If n = 2 Then
IsPrime = True
ElseIf n <= 1 Or n Mod 2 = 0 Then
IsPrime = False
Else
IsPrime = True
For i = 3 To Int(Sqr(n)) Step 2
If n Mod i = 0 Then
IsPrime = False
Exit For
End If
Next
End If
End Function
</syntaxhighlight>
{{Out}}
<pre>
Largest LTP from 1..1000000: 998443
Largest RTP from 1..1000000: 739399
Elapse Time(seconds) : 49
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
var limit = 999999
var c = Int.primeSieve(limit, false)
var leftFound = false
var rightFound = false
System.print("Largest truncatable primes less than a million:")
var i = limit
while (i > 2) {
if (!c[i]) {
if (!rightFound) {
var p = (i/10).floor
while (p > 0) {
if (p%2 == 0 || c[p]) break
p = (p/10).floor
}
if (p == 0) {
System.print(" Right truncatable prime = %(Fmt.dc(0, i))")
rightFound = true
if (leftFound) return
}
}
if (!leftFound) {
var q = i.toString[1..-1]
if (!q.contains("0")) {
var p = Num.fromString(q)
while (q.count > 0) {
if (p%2 == 0 || c[p]) break
q = q[1..-1]
p = Num.fromString(q)
}
if (q == "") {
System.print(" Left truncatable prime = %(Fmt.dc(0, i))")
leftFound = true
if (rightFound) return
}
}
}
}
i = i - 2
}</syntaxhighlight>
{{out}}
<pre>
Largest truncatable primes less than a million:
Left truncatable prime = 998,443
Right truncatable prime = 739,399
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">code CrLf=9, IntOut=11;
func Prime(P); \Return true if P is a prime number
int P; \(1 is not prime, but 2 is, etc.)
int I;
[if P<=1 then return false; \negative numbers are not prime
for I:= 2 to sqrt(P) do
if rem(P/I) = 0 then return false;
return true;
];
func RightTrunc(N); \Return largest right-truncatable prime < one million
int N;
int M;
[for N:= 1_000_000-1 downto 2 do
[M:= N;
loop [if not Prime(M) then quit;
M:= M/10;
if rem(0) = 0 then quit; \no zeros allowed
if M=0 then return N;
];
];
];
func LeftTrunc(N); \Return largest left-truncatable prime < one million
int N;
int M, P;
[for N:= 1_000_000-1 downto 2 do
[M:= N;
P:=100_000;
loop [if not Prime(M) then quit;
M:= rem(M/P);
P:= P/10;
if M<P then quit; \no zeros allowed
if M=0 then return N;
];
];
];
[IntOut(0, LeftTrunc); CrLf(0);
IntOut(0, RightTrunc); CrLf(0);
]</syntaxhighlight>
Output:
<pre>
998443
739399
</pre>
=={{header|zkl}}==
Using [[Extensible prime generator#zkl]] and a one meg bucket of bytes, construct a yes/no lookup table for all primes <= one million (<80,000).
<syntaxhighlight lang="zkl">const million=0d1_000_000;
var pTable=Data(million+1,Int).fill(0); // actually bytes, all zero
primes:=Utils.Generator(Import("sieve").postponed_sieve);
while((p:=primes.next())<million){ pTable[p]=1; }
fcn rightTrunc(n){
while(n){ if(not pTable[n]) return(False); n/=10; }
True
}
fcn leftTrunc(n){ // 999,907 is not allowed
ns:=n.toString(); if (ns.holds("0")) return(False);
while(ns){ if(not pTable[ns]) return(False); ns=ns[1,*]; }
True
}</syntaxhighlight>
<syntaxhighlight lang="zkl">[million..0,-1].filter1(rightTrunc):
"%,d is a right truncatable prime".fmt(_).println();
[million..0,-1].filter1(leftTrunc):
"%,d is a left truncatable prime".fmt(_).println();</syntaxhighlight>
{{out}}
<pre>
739,399 is a right truncatable prime
998,443 is a left truncatable prime
</pre>
| |||