結果
問題 | No.12 限定された素数 |
ユーザー | mastersatoshi |
提出日時 | 2015-08-04 13:53:07 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 488 ms / 5,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 2,463 ms |
コンパイル使用メモリ | 80,284 KB |
実行使用メモリ | 82,056 KB |
最終ジャッジ日時 | 2024-05-03 09:30:36 |
合計ジャッジ時間 | 14,237 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 356 ms
75,628 KB |
testcase_01 | AC | 441 ms
81,720 KB |
testcase_02 | AC | 357 ms
75,832 KB |
testcase_03 | AC | 408 ms
76,796 KB |
testcase_04 | AC | 432 ms
80,976 KB |
testcase_05 | AC | 456 ms
81,840 KB |
testcase_06 | AC | 459 ms
81,612 KB |
testcase_07 | AC | 453 ms
81,608 KB |
testcase_08 | AC | 440 ms
81,772 KB |
testcase_09 | AC | 432 ms
81,672 KB |
testcase_10 | AC | 443 ms
81,772 KB |
testcase_11 | AC | 460 ms
81,724 KB |
testcase_12 | AC | 466 ms
81,820 KB |
testcase_13 | AC | 456 ms
81,384 KB |
testcase_14 | AC | 439 ms
81,428 KB |
testcase_15 | AC | 452 ms
81,440 KB |
testcase_16 | AC | 488 ms
82,056 KB |
testcase_17 | AC | 361 ms
75,836 KB |
testcase_18 | AC | 370 ms
75,932 KB |
testcase_19 | AC | 359 ms
75,816 KB |
testcase_20 | AC | 421 ms
81,092 KB |
testcase_21 | AC | 424 ms
81,620 KB |
testcase_22 | AC | 370 ms
76,120 KB |
testcase_23 | AC | 383 ms
75,952 KB |
testcase_24 | AC | 373 ms
75,936 KB |
testcase_25 | AC | 461 ms
81,572 KB |
ソースコード
import java.io.*; import java.util.*; public class Main { static boolean[] a = new boolean[10]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { a[sc.nextInt()] = true; } ArrayList<Integer> prime = getPrime(); int miniMax = Integer.MIN_VALUE; for (int i = 0; i < prime.size(); i++) { TreeMap<Integer, Integer> nums = getNum(prime.get(i)); if (!isTrue(nums)) { continue; } int miniIndex = i; int maxIndex = i; i++; boolean[] tmpA = a.clone(); cieve(tmpA, nums); for (; i < prime.size(); i++) { nums = getNum(prime.get(i)); if (!isTrue(nums)) { break; } maxIndex = i; cieve(tmpA, nums); } boolean include = true; for (boolean a : tmpA) { if (a) { include = false; break; } } if (!include) { continue; } int min; int max; if (miniIndex == 0) { min = 1; } else { min = prime.get(miniIndex - 1) + 1; } if (maxIndex == prime.size() - 1) { max = 5000000; } else { max = prime.get(maxIndex + 1) - 1; } if (miniMax < max - min) { miniMax = max - min; } } if (miniMax == Integer.MIN_VALUE) { System.out.println(-1); } else { System.out.println(miniMax); } } private static ArrayList<Integer> getPrime() { boolean[] cieve = new boolean[5000001]; cieve[0] = true; cieve[1] = true; int max = (int) Math.sqrt(5000000); for (int i = 2; i <= max; i++) { if (cieve[i]) { continue; } for (int j = i; j * i < 5000000; j++) { cieve[j * i] = true; } } ArrayList<Integer> ret = new ArrayList(); for (int i = 0; i < 5000000; i++) { if (!cieve[i]) { ret.add(i); } } return ret; } private static TreeMap<Integer, Integer> getNum(int num) { TreeMap<Integer, Integer> ret = new TreeMap(); while (num != 0) { ret.put(num % 10, 0); num = num / 10; } return ret; } private static boolean isTrue(TreeMap<Integer, Integer> nums) { for (int num : nums.keySet()) { if (!a[num]) { return false; } } return true; } private static void cieve(boolean[] tmpA, TreeMap<Integer, Integer> nums) { for (int num : nums.keySet()) { tmpA[num] = false; } } }