結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2016-01-03 12:12:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 313 ms / 5,000 ms |
コード長 | 1,239 bytes |
コンパイル時間 | 284 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-10-01 15:39:54 |
合計ジャッジ時間 | 3,330 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import array import math def primes_by_eratosthenes(limit): """ Generate the sequence of prime numbers by Eratosthenes' method. :param limit: The maximum intenger (> 1) to be examined. :type limit: int :return: the sequence of prime numbers :rtype: an instance of :class:`array.array` """ search_list = array.array("Q", range(2, limit + 1)) primes = array.array("Q") while True: p = search_list.pop(0) primes.append(p) if p > math.sqrt(limit): break else: search_list = array.array("Q", filter( lambda x: x % p != 0, search_list)) primes.extend(search_list) return primes def judge(n): dp = array.array("B", [True, True]) primes = primes_by_eratosthenes(n) for m in range(2, n + 1): for p in primes: if p > m: dp.append(False) break elif not dp[m - p]: dp.append(True) break else: continue else: dp.append(False) return dp[n] if __name__ == "__main__": print("Win" if judge(int(input())) else "Lose")