Truncatable primes: Difference between revisions
Content deleted Content added
CoffeeScript |
|||
Line 335:
(map vector ["left truncatable: " "right truncatable: "] ,))
(["left truncatable: " 998443] ["right truncatable: " 739399])</lang>
=={{header|CoffeeScript}}==
<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
max_digit n, f
else
left = Math.floor n / 10
right = n % 10
while left > 0
left = max_right_truncatable_number left, f
while right > 0
candidate = left * 10 + right
return candidate if f(candidate)
right -= 1
left -= 1
right = 9
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"
max_digit = (n, f) ->
# return max digit <= n where fn(fn) is true
candidate = n
while candidate > 0
return candidate if f(candidate)
candidate -= 1
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)
<lang>
output
<lang>
> coffee truncatable_prime.coffee
right 739399
left 998443
</lang>
=={{header|D}}==
| |||