import scala.collection.mutable import scala.io.StdIn object Problem308 { def primesIn(max: Int): Seq[Int] = { val a = Array.fill(max + 1)(false) for { i <- 2 to max if !a(i) } yield { (i + i to max by i).foreach(a(_) = true) i } } def isPrime(n: BigInt): Boolean = n.isProbablePrime(50) def canGoal(n: Int, mod: Int): Boolean = { val start = 1 val goal = n val clear = Array.fill(n + 1)(false) val primes: Seq[Int] = primesIn(n) if (primes.contains(n) || primes.contains(mod + 1)) return false def canMoveTo(i: Int): Boolean = !primes.contains(i) def left(i: Int): Option[Int] = { val next = i - 1 if (canMoveTo(next) && next % mod != 0 && next >= start) Some(next) else None } def right(i: Int): Option[Int] = { val next = i + 1 if (canMoveTo(next) && i % mod != 0 && next <= goal) Some(next) else None } def up(i: Int): Option[Int] = { val next = i - mod if (canMoveTo(next) && next >= start) Some(next) else None } def down(i: Int): Option[Int] = { val next = i + mod if (canMoveTo(next) && next <= goal) Some(next) else None } val queue = mutable.Queue[Int]() queue += start while (queue.nonEmpty) { val p = queue.dequeue() def a: (Int) => Unit = { x => if (!clear(x)) { queue += x clear(x) = true } } left(p).foreach(a) right(p).foreach(a) up(p).foreach(a) down(p).foreach(a) } clear(goal) } def blute(n: Int): Option[Int] = { (1 to n) find { mod => canGoal(n, mod) } } def proc(n: BigInt): BigInt = { if (n <= 25) { BigInt(blute(n.toInt).get) } else { if (isPrime(n - 8) && (n % 8 == 1 || isPrime(n - 1))) 14 else 8 } } def main(args: Array[String]) { val n = BigInt(StdIn.readLine()) val result: BigInt = proc(n) println(result) } }