結果

問題 No.308 素数は通れません
ユーザー くわいくわい
提出日時 2015-12-12 13:38:08
言語 Scala(Beta)
(3.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,969 bytes
コンパイル時間 6,595 ms
コンパイル使用メモリ 243,784 KB
最終ジャッジ日時 2024-11-14 19:31:01
合計ジャッジ時間 7,141 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
-- [E040] Syntax Error: Main.scala:81:32 ---------------------------------------
81 |  def main(args: Array[String]) {
   |                                ^
   |                                '=' expected, but '{' found
1 error found

ソースコード

diff # 

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)
  }
}
0