Truncatable primes: Difference between revisions
(No zeroes are allowed in truncatable primes.) |
(→Tcl: Added implementation) |
||
Line 58: | Line 58: | ||
'''Sample Output''' |
'''Sample Output''' |
||
<pre>(998443, 739399)</pre> |
<pre>(998443, 739399)</pre> |
||
=={{header|Tcl}}== |
|||
<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 |
|||
} |
|||
}</lang> |
|||
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> |
Revision as of 08:20, 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. 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.
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)
Tcl
<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
}
}</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