結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー yuppe19 😺
提出日時 2015-05-02 19:55:28
言語 Nim
(2.2.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 662 bytes
コンパイル時間 3,751 ms
コンパイル使用メモリ 65,664 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 15:31:54
合計ジャッジ時間 4,515 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils, sequtils, math

proc sieve(n: int): seq[int] =
  var
    is_prime:seq[bool] = newSeqWith(n+1, true)
    sq = n.float.sqrt.int
  is_prime[0] = false
  is_prime[1] = false
  for i in 2.. sq:
    if is_prime[i]:
      for j in countup(i*i, n, i):
        is_prime[j] = false
  result = newSeq[int](0)
  for i in 0.. n:
    if is_prime[i]: result.add(i)

var
  n:int
  primes:seq[int]
  win:seq[bool]

n = stdin.readLine.parseInt
primes = sieve(n)
win = newSeqWith(n+2, false)
win[0] = true
win[1] = true

for i in 2.. n:
  for p in primes:
    if p > i: break
    if not win[i-p]:
      win[i] = true
      break

echo if win[n]: "Win" else: "Lose"
0