結果
問題 | No.843 Triple Primes |
ユーザー | hiromi_ayase |
提出日時 | 2019-06-28 21:44:10 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 330 ms / 2,000 ms |
コード長 | 4,445 bytes |
コンパイル時間 | 4,135 ms |
コンパイル使用メモリ | 91,152 KB |
実行使用メモリ | 61,000 KB |
最終ジャッジ日時 | 2023-10-19 17:40:24 |
合計ジャッジ時間 | 15,023 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
54,444 KB |
testcase_01 | AC | 330 ms
61,000 KB |
testcase_02 | AC | 91 ms
54,444 KB |
testcase_03 | AC | 95 ms
55,096 KB |
testcase_04 | AC | 95 ms
55,076 KB |
testcase_05 | AC | 96 ms
54,984 KB |
testcase_06 | AC | 97 ms
54,692 KB |
testcase_07 | AC | 282 ms
58,948 KB |
testcase_08 | AC | 303 ms
60,904 KB |
testcase_09 | AC | 327 ms
60,744 KB |
testcase_10 | AC | 278 ms
60,748 KB |
testcase_11 | AC | 307 ms
60,972 KB |
testcase_12 | AC | 323 ms
60,652 KB |
testcase_13 | AC | 315 ms
60,792 KB |
testcase_14 | AC | 319 ms
60,876 KB |
testcase_15 | AC | 280 ms
60,844 KB |
testcase_16 | AC | 283 ms
60,884 KB |
testcase_17 | AC | 80 ms
54,456 KB |
testcase_18 | AC | 80 ms
54,440 KB |
testcase_19 | AC | 81 ms
54,448 KB |
testcase_20 | AC | 167 ms
58,696 KB |
testcase_21 | AC | 142 ms
58,712 KB |
testcase_22 | AC | 224 ms
56,720 KB |
testcase_23 | AC | 220 ms
58,532 KB |
testcase_24 | AC | 162 ms
58,664 KB |
testcase_25 | AC | 158 ms
58,636 KB |
testcase_26 | AC | 327 ms
60,752 KB |
testcase_27 | AC | 113 ms
57,696 KB |
testcase_28 | AC | 316 ms
60,976 KB |
testcase_29 | AC | 170 ms
58,552 KB |
testcase_30 | AC | 321 ms
60,756 KB |
testcase_31 | AC | 125 ms
58,140 KB |
testcase_32 | AC | 112 ms
57,772 KB |
testcase_33 | AC | 180 ms
58,504 KB |
testcase_34 | AC | 217 ms
58,688 KB |
testcase_35 | AC | 329 ms
60,832 KB |
testcase_36 | AC | 151 ms
58,660 KB |
testcase_37 | AC | 268 ms
60,748 KB |
testcase_38 | AC | 235 ms
60,752 KB |
testcase_39 | AC | 326 ms
60,984 KB |
testcase_40 | AC | 79 ms
54,568 KB |
testcase_41 | AC | 79 ms
54,444 KB |
testcase_42 | AC | 286 ms
60,852 KB |
testcase_43 | AC | 317 ms
60,656 KB |
ソースコード
import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Main { private static void solve() { int n = ni(); int[] primes = sieveEratosthenes(n); Set<Integer> sq = new HashSet<>(); for (int p : primes) { sq.add(p); } int m = primes.length; int ret = 0; for (int i = 0; i < m; i ++) { for (int j = 0; j < m && primes[j] * primes[j] <= n * 2; j ++) { if (sq.contains(primes[j] * primes[j] - primes[i])) { ret ++; } } } System.out.println(ret); } public static int[] sieveEratosthenes(int n) { if (n <= 32) { int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; for (int i = 0; i < primes.length; i++) { if (n < primes[i]) { return Arrays.copyOf(primes, i); } } return primes; } int u = n + 32; double lu = Math.log(u); int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)]; ret[0] = 2; int pos = 1; int[] isnp = new int[(n + 1) / 32 / 2 + 1]; int sup = (n + 1) / 32 / 2 + 1; int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; for (int tp : tprimes) { ret[pos++] = tp; int[] ptn = new int[tp]; for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31); for (int j = 0; j < sup; j += tp) { for (int i = 0; i < tp && i + j < sup; i++) { isnp[j + i] |= ptn[i]; } } } // 3,5,7 // 2x+3=n int[] magic = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14}; int h = n / 2; for (int i = 0; i < sup; i++) { for (int j = ~isnp[i]; j != 0; j &= j - 1) { int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27]; int p = 2 * pp + 3; if (p > n) break; ret[pos++] = p; if ((long) p * p > n) continue; for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q; } } return Arrays.copyOf(ret, pos); } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = args.length > 0 ? args[0] : null; if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }