結果
問題 |
No.12 限定された素数
|
ユーザー |
![]() |
提出日時 | 2014-12-22 15:27:26 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 276 ms / 5,000 ms |
コード長 | 1,852 bytes |
コンパイル時間 | 2,107 ms |
コンパイル使用メモリ | 79,352 KB |
実行使用メモリ | 56,116 KB |
最終ジャッジ日時 | 2024-11-24 07:37:03 |
合計ジャッジ時間 | 9,770 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
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; } }