require "prime" def ok n,w stack = [] vis = n.times.map { false } stack.push 1 while stack.size != 0 c = stack.pop return true if c == n vis[c] = true if c%w != 0 && !vis[c+1] && !$isprime[c+1] stack.push c+1 end if c%w != 1 && !vis[c-1] && !$isprime[c-1] stack.push c-1 end if c-w >= 1 && !vis[c-w] && !$isprime[c-w] stack.push c-w end if c+w <= n && !vis[c+w] && !$isprime[c+w] stack.push c+w end end false end n = gets.to_i $isprime = n.times.map { false } Prime.each(n) { |p| $isprime[p] = true } n.times.each do |w| next if w < 3 if ok n,w puts w exit end end puts n