結果
問題 | No.12 限定された素数 |
ユーザー | ぴろず |
提出日時 | 2014-12-22 15:27:26 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 290 ms / 5,000 ms |
コード長 | 1,852 bytes |
コンパイル時間 | 2,434 ms |
コンパイル使用メモリ | 78,952 KB |
実行使用メモリ | 65,776 KB |
最終ジャッジ日時 | 2024-05-03 08:55:22 |
合計ジャッジ時間 | 9,568 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 283 ms
65,188 KB |
testcase_01 | AC | 255 ms
65,592 KB |
testcase_02 | AC | 240 ms
65,304 KB |
testcase_03 | AC | 252 ms
65,776 KB |
testcase_04 | AC | 234 ms
65,316 KB |
testcase_05 | AC | 274 ms
65,396 KB |
testcase_06 | AC | 242 ms
65,200 KB |
testcase_07 | AC | 253 ms
65,484 KB |
testcase_08 | AC | 252 ms
65,388 KB |
testcase_09 | AC | 244 ms
65,188 KB |
testcase_10 | AC | 259 ms
65,704 KB |
testcase_11 | AC | 232 ms
65,664 KB |
testcase_12 | AC | 225 ms
65,408 KB |
testcase_13 | AC | 252 ms
65,456 KB |
testcase_14 | AC | 248 ms
65,580 KB |
testcase_15 | AC | 237 ms
65,528 KB |
testcase_16 | AC | 256 ms
65,512 KB |
testcase_17 | AC | 249 ms
65,432 KB |
testcase_18 | AC | 234 ms
65,256 KB |
testcase_19 | AC | 218 ms
64,684 KB |
testcase_20 | AC | 290 ms
65,740 KB |
testcase_21 | AC | 257 ms
65,268 KB |
testcase_22 | AC | 245 ms
65,288 KB |
testcase_23 | AC | 236 ms
65,384 KB |
testcase_24 | AC | 252 ms
65,324 KB |
testcase_25 | AC | 252 ms
65,356 KB |
ソースコード
package no012; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); boolean[] use = new boolean[10]; for(int i=0;i<n;i++) { use[sc.nextInt()] = true; } int[] digits = new int[10]; ArrayList<Integer> primes = Sieve.primeList(5000000); int j = 0; int ans = -1; for(int i=0;i<primes.size();i++) { while(j <= primes.size()) { boolean expand = true; boolean ok = true; for(int k=0;k<10;k++) { if (!use[k] && digits[k] > 0) { expand = false; ok = false; break; } if (use[k] && digits[k] == 0) { ok = false; } } if (ok) { int k = i == 0 ? 1 : primes.get(i-1) + 1; int l = j == primes.size() ? 5000000 : primes.get(j) - 1; ans = Math.max(ans,l-k); } if (!expand) { break; } if (j == primes.size()) { break; } int p = primes.get(j); while(p > 0) { digits[p%10]++; p/=10; } //System.out.println(primes.get(i) + "," + primes.get(j)); j++; } int p = primes.get(i); while(p > 0) { digits[p%10]--; p/=10; } } System.out.println(ans); } } class Sieve { public static boolean[] isPrimeArray(int max) { boolean[] isPrime = new boolean[max+1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for(int i=2;i*i<=max;i++) { if (isPrime[i]) { int j = i * 2; while(j<=max) { isPrime[j] = false; j += i; } } } return isPrime; } public static ArrayList<Integer> primeList(int max) { boolean[] isPrime = isPrimeArray(max); ArrayList<Integer> primeList = new ArrayList<>(); for(int i=2;i<=max;i++) { if (isPrime[i]) { primeList.add(i); } } return primeList; } }