Truncatable primes: Difference between revisions
→{{header|Python}}: first draft |
|||
Line 8: | Line 8: | ||
== {{header|J}} == |
== {{header|J}} == |
||
<lang j> isprime=: 1&p: |
<lang j> isprime=: 1&p: |
||
primesbelow=: (#~ isprime)@i.@- NB. gives primes below right arg, from biggest to smallest |
|||
filterprimes=: #~ isprime |
|||
primesbelow=: filterprimes@i.@- |
|||
isprimeRT=: ([: *./@:isprime 0&".\)@":"0 |
isprimeRT=: ([: *./@:isprime 0&".\)@":"0 |
||
isprimeLT=: ([: *./@:isprime 0&".\.)@":"0 |
isprimeLT=: ([: *./@:isprime 0&".\.)@":"0 |
||
Line 16: | Line 15: | ||
999907 |
999907 |
||
({~ i.&1@:isprimeRT) primesbelow 1e6 |
({~ i.&1@:isprimeRT) primesbelow 1e6 |
||
739399</lang> |
|||
Or cleaned up a bit more using an adverb: |
|||
<lang j> getfirst=: 1 : 'y {~ (u i. 1:) y' |
|||
isprimeLT getfirst primesbelow 1e6 |
|||
999907 |
|||
isprimeRT getfirst primesbelow 1e6 |
|||
739399</lang> |
739399</lang> |
||
Revision as of 01:31, 9 September 2010
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.
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:
primesbelow=: (#~ isprime)@i.@- NB. gives primes below right arg, from biggest to smallest isprimeRT=: ([: *./@:isprime 0&".\)@":"0 isprimeLT=: ([: *./@:isprime 0&".\.)@":"0
({~ i.&1@:isprimeLT) primesbelow 1e6
999907
({~ i.&1@:isprimeRT) primesbelow 1e6
739399</lang>
Or cleaned up a bit more using an adverb: <lang j> getfirst=: 1 : 'y {~ (u i. 1:) y'
isprimeLT getfirst primesbelow 1e6
999907
isprimeRT getfirst primesbelow 1e6
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)