結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2015-12-20 09:40:31 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 225 ms / 5,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 2,364 ms |
コンパイル使用メモリ | 79,056 KB |
実行使用メモリ | 54,624 KB |
最終ジャッジ日時 | 2024-10-01 15:39:34 |
合計ジャッジ時間 | 5,614 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import java.util.*; import java.math.*; public class Main{ public static void main(String... args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); System.out.println(Calc(n)); } public static String Calc(int n){ LinkedList<Integer> prime = eratosthenes(n); boolean[] judge = new boolean[n+1]; judge[0] = true; judge[1] = true; for(int i = 4; i <= n; i++){ for(int p:prime){ if(0<=i-p && !judge[i-p])judge[i] = true; } } return (judge[n])?"Win":"Lose"; } public static LinkedList<Integer> eratosthenes(int n){ LinkedList<Integer> list = new LinkedList<Integer>(); LinkedList<Integer> result = new LinkedList<Integer>(); list.add(2); for(int i = 3; i <= n;i+=2){ list.add(i); } double limit = Math.sqrt(n); double head = 0.0; int nowHead; while(head < limit){ head = (double)list.get(0); nowHead = (int)head; result.add(nowHead); for(Iterator<Integer> it = list.iterator(); it.hasNext();){ int num = it.next(); if(num%nowHead == 0){ it.remove(); } } } for(Iterator<Integer> it = list.iterator(); it.hasNext();){ result.add(it.next()); } return result; } }