読者です 読者をやめる 読者になる 読者になる

mu chance or much chance ?

日々の戯れ言

Project Euler 37

Project Euler

Problem37を解きました.

  • Truncatable primes

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.

https://projecteuler.net/problem=37

問題は「右から1つずつ切り詰めても,左から1つずつ切り詰めても素数になるような素数の総和を求めよ.ただし1桁の素数は対象外とする」.

require 'prime'
count = 0
sum = 0
num = 10
while count < 11

  flag = false
  k = num

  unless Prime.prime?(num)
    num += 1
    next
  end

  loop do
    a = Math.log10(k).to_i
    b = k / (10**a)
    k -= b * (10**a)
    break if k.zero?
    unless Prime.prime?(k)
      flag = true
      break
    end
  end

  if flag
    num += 1
    next
  end

  k = num
  loop do
    k /= 10
    break if k.zero?
    unless Prime.prime?(k)
      flag = true
      break
    end
  end

  unless flag
    sum += num
    count += 1
  end
  num += 1
end

p sum

左右の切り詰め方がわかれば解けますね.