# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041
#
# 最大値なので，9桁Pandigital数から桁数を減らしていって
# 素数が見つかったら桁数内で最大値を取ればよい．

require 'prime'

9.downto(1) do |k|
  # k桁のPandigital数を全て生成して素数があれば最大値を取る.(なければ-1)
  max_prime = (1 .. k).map(&:to_s).permutation(k).reduce(-1) {|max, pn|
    pn = pn.join.to_i
    Prime.prime?(pn) ? [max, pn].max : max
  }
  if (max_prime > 0)
    # 素数があれば終了
    puts max_prime
    break
  end
end