Truncatable primes

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.

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.

J

<lang j> isprime=: 1&p:

  nozeros=: '0'&(-.@e.)
  listprimesbelow=: (#~ isprime)@i.@-        NB. (from biggest to smallest)
  isprimeRT=: ([: *./@isprime 0&".\)@":"0
  isprimeLT0=: ([: *./@isprime 0&".\.)@":"0  NB. leading zeros allowed
  isprimeLT=: (nozeros *. [: *./@isprime 0&".\.)@":"0

  getfirst=: 1 : 'y {~ (u i. 1:) y'          NB. an adverb (modifies verb to its left)

  primes=: listprimesbelow 1e6
  isprimeLT getfirst primes

998443

  isprimeLT0 getfirst primes

999907

  isprimeRT getfirst primes

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