結果
問題 | No.12 限定された素数 |
ユーザー |
![]() |
提出日時 | 2015-08-04 13:53:07 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 452 ms / 5,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 2,018 ms |
コンパイル使用メモリ | 80,176 KB |
実行使用メモリ | 70,280 KB |
最終ジャッジ日時 | 2024-11-24 08:23:41 |
合計ジャッジ時間 | 13,280 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
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; } } }