Project Euler Problem 37
問題
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3. Find the sum of the only eleven primes that are both truncatable from left to right and right to left. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
ソース
max = 1000000 $prime = Array.new(max, 1) $prime[0..1] = [0, 0] i = 2 while i < Math.sqrt(max).to_i + 1 do (i + i).step(max, i){|x| $prime[x] = 0} i += $prime[(i + 1)..max].index(1) + 1 end class Integer def interesting_left? n = self while n > 0 return false if $prime[n] == 0 n %= 10 ** (n.to_s.size - 1) end true end def interesting_right? n = self while n > 0 return false if $prime[n] == 0 n /= 10 end true end def interesting? self.interesting_left? && self.interesting_right? end end sum = 0 $prime.each_index{|i| if i >= 10 && !$prime[i].zero? sum += (i.interesting? ? i : 0) end } puts sum
解答
748317
感想
んまぁ実装すればいいだけかな。。
特に難しい部分はない