Truncatable primes: Difference between revisions

From Rosetta Code
Content added Content deleted
m (sort)
(Added Java Implementation.)
Line 321: Line 321:
>./ step&digits^:5 seed NB. right truncatable
>./ step&digits^:5 seed NB. right truncatable
739399</lang>
739399</lang>

=={{header|Java}}==

<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 Truncable 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 Truncable Prime?
if(rightTrunc == -1)
{
int right = prime;
while(right > 0 && primeList.get(right >> 1)) right /= 10;
if(right == 0) rightTrunc = prime;
}

//Already found Left Truncable Prime?
if(leftTrunc == -1 )
{
//Left Truncation
String left = String.valueOf(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 Truncable : " + leftTrunc);
System.out.println("Right Truncable : " + rightTrunc);
}
}
</lang>
Output :
<pre>
Left Truncable : 998443
Right Truncable : 796339
</pre>

=={{header|Lua}}==
=={{header|Lua}}==
<lang lua>max_number = 1000000
<lang lua>max_number = 1000000

Revision as of 10:27, 30 December 2010

Task
Truncatable primes
You are encouraged to solve this task according to the task description, using any language you may know.

A truncatable prime is prime number that when you successively remove digits from one end of the prime, you are left with a new prime number; for example, 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.

The task is to find the largest left-truncatable and right-truncatable primes less than one million.

C.f: Sieve of Eratosthenes; Truncatable Prime from Mathworld.

Ada

<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; </lang> Sample output: 

Largest LTP from 1..1000000: 998443
Largest RTP from 1..1000000: 739399

D

<lang d>import std.stdio, std.math, std.string, std.conv;

bool isPrime(int n) { 

 if (n <= 1)
   return false;
 foreach (i; 2 .. cast(int)sqrt(cast(real)n) + 1)
   if (!(n % i))
     return false;
 return true;

}

bool isLeftTruncatablePrime(int n) { 

 string s = to!string(n);
 if (indexOf(s, '0') != -1)
   return false;
 foreach (i; 0 .. s.length)
   if (!isPrime(to!int(s[i .. $])))
     return false;
 return true;

}

bool isRightTruncatablePrime(int n) { 

 string s = to!string(n);
 if (indexOf(s, '0') != -1)
   return false;
 foreach (i; 0 .. s.length)
   if (!isPrime(to!int(s[0 .. i+1])))
     return false;
 return true;

}

void main() { 

 enum int n = 1_000_000;
 foreach_reverse (i; 2 .. n)
   if (isLeftTruncatablePrime(i)) {
     writeln("Largest left-truncatable prime in 2 .. ", n, ": ", i);
     break;
   }
 foreach_reverse (i; 2 .. n)
   if (isRightTruncatablePrime(i)) {
     writeln("Largest right-truncatable prime in 2 .. ", n, ": ", i);
     break;
   }

}</lang> Output: 

Largest left-truncatable prime in 2 .. 1000000: 998443
Largest right-truncatable prime in 2 .. 1000000: 739399

Fortran

Works with: Fortran version 95 and later

<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</lang> Output 

Largest left truncatable prime below 1000000 is 998443
Largest right truncatable prime below 1000000 is 739399

Haskell

Using

Library: Primes

from HackageDB

<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</lang>

Output: <lang haskell>*Main> main Left truncatable 998443 Right truncatable 739399</lang>

Interpretation of the J contribution: <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</lang> Output: <lang haskell>*Main> maximum $ primesTruncatable righT !! 5 739399

  • Main> maximum $ primesTruncatable lefT !! 5

998443</lang>

Icon and Unicon

Icon

<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</lang>

Sample output:

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

Unicon

The Icon solution works in Unicon.

J

Truncatable primes may be constructed by starting with a set of one digit prime numbers and then repeatedly adding a non-zero digit (using the cartesian product of digit sequences) and, at each step, selecting the prime numbers which result.

In other words, given:

<lang j>selPrime=: #~ 1&p: seed=: selPrime digits=: 1+i.9 step=: selPrime@,@:(,&.":/&>)@{@;</lang>

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:

<lang j> >./ digits&step^:5 seed NB. left truncatable 998443 

  >./ step&digits^:5 seed  NB. right truncatable

739399</lang>

Java

<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 Truncable 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 Truncable Prime? if(rightTrunc == -1) { int right = prime; while(right > 0 && primeList.get(right >> 1)) right /= 10; if(right == 0) rightTrunc = prime; }

//Already found Left Truncable Prime? if(leftTrunc == -1 ) { //Left Truncation String left = String.valueOf(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 Truncable : " + leftTrunc); System.out.println("Right Truncable : " + rightTrunc); } } </lang> Output : 

Left  Truncable : 998443
Right Truncable : 796339

Lua

<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 )</lang>

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. <lang>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)]</lang>

Perl 6

Works with: Rakudo Star version 2010.09

This uses a fairly naive isprime routine. It works but is slow.

<lang perl6> use v6; my %cache = <2 3 5 7 11 13 17 19 23> >>=>>> 1;

sub isprime ($test) { 

   return %cache{$test} if defined %cache{$test};
   return (%cache{$test} = 0) if $test <= 25;
   my $r = floor($test ** .5);
   return (%cache{$test} = 0) unless $test % $_ for (2, 3, * + 2 ... * >= $r);
   return (%cache{$test} = 1);

}

sub trunc_prime ($type, $limit is copy) { 

   $limit += ($limit % 2 ?? 0 !! 1);
   for ($limit, * - 2 ... * < 2 ) -> $loop {
       next if $loop ~~ /0/; # No zeros allowed 
       my $this = $loop;
       while $this.&isprime {
           $this.=subst($type, );
           return $loop unless $this;
       }
   }

}

say "Largest Left Truncatable Prime < 1000000: ",trunc_prime(rx/^\d/, 1000000); say "Largest Right Truncatable Prime < 1000000: ",trunc_prime(rx/\d$/, 1000000); </lang> Output: 

Largest Left  Truncatable Prime < 1000000: 998443
Largest Right Truncatable Prime < 1000000: 739339

PicoLisp

<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) )</lang>

Output: 

-> (998443 . 739399)

PowerShell

<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"
   }

}</lang>

PureBasic

<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)</lang>

Python

<lang python>maxprime = 1000000

def primes(n): 

   multiples = set()
   prime = []
   for i in range(2, n+1):
       if i not in multiples:
           prime.append(i)
           multiples.update(set(range(i*i, n+1, i)))
   return prime

def truncatableprime(n): 

   'Return a longest left and right truncatable primes below n'
   primelist = [str(x) for x in primes(n)[::-1]]
   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):
           truncateleft = int(n)
           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):
           truncateright = int(n)
           break
   return truncateleft, truncateright

print(truncatableprime(maxprime))</lang>

Sample Output 

(998443, 739399)

REXX

<lang REXX> /*find largest left- & right-truncatable primes < 1 million.*/ x.=0 /*placeholders for primes. */ p.=999 /*default value for P.n */ p.1= 2; x.2=1 /*1st prime: two. */ p.2= 3; x.3=1 /*2nd prime: three. */ p.3= 5; x.5=1 /*3rd prime: five. */ p.4= 7; x.7=1 /*4th prime: seven. */ p.5=11; x.11=1 /*5th prime: eleven. */ n=5 /*number of primes so far. */ 

 do j=p.n+2 by 2 to 1000000           /*find all primes <1000000.   */
 if j//3      ==0 then iterate        /*divisible by three?         */
 if right(j,1)==5 then iterate        /*right-most digit a five?    */
 if j//7      ==0 then iterate        /*divisible by seven?         */
 if j//11     ==0 then iterate        /*divisible by eleven?        */
                                      /*the above 4 lines saves time*/
   do k=6                             /*divide by known odd primes. */
   if p.k**2>j then leave             /*only go up to sqrt(J).      */
   if j//p.k==0 then iterate j        /*divisible by X?  Not prime. */
   end

 n=n+1                                /*bump number of primes found.*/
 p.n=j                                /*assign to sparse array.     */
 x.j=1                                /*indicate that J is a prime. */
 end

say 'The last prime is' p.n "("n 'primes under one million).' say copies('-',66) /*show a separator. */ lp=0 

 do j=1 for n                         /*find left-trunc. primes.    */
 y=p.j; g=y
 if pos(0,y)\==0 then iterate         /*if prime contains a 0, nope.*/

   do k=1 for length(y)-1             /*test for prime, skip whole #*/
   g=right(y,k); if \x.g then iterate j
   end

 lp=max(lp,y)                         /*choose the maximum so far.  */
 end

rp=0 

 do j=1 for n                         /*find left-trunc. primes.    */
 y=p.j; g=y
 if pos(0,y)\==0 then iterate         /*if prime contains a 0, nope.*/

   do k=1 for length(y)-1             /*test for prime, skip whole #*/
   g=left(y,k); if \x.g then iterate j
   end

 rp=max(rp,y)                         /*choose the maximum so far.  */
 end

say 'The largest left-truncatable prime is' lp '(under one million).' say 'The largest right-truncatable prime is' rp '(under one million).'

</lang> Output: 

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).

Tcl

<lang tcl>package require Tcl 8.5

  1. 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

}

  1. 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 

   }

}</lang> Output: 

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
Retrieved from "https://rosettacode.org/wiki/Truncatable_primes?oldid=156863"