結果
問題 | No.843 Triple Primes |
ユーザー | Tomoya |
提出日時 | 2019-06-28 23:03:03 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 2,256 bytes |
コンパイル時間 | 3,886 ms |
コンパイル使用メモリ | 79,064 KB |
実行使用メモリ | 84,428 KB |
最終ジャッジ日時 | 2023-10-19 17:51:08 |
合計ジャッジ時間 | 20,523 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 306 ms
82,492 KB |
testcase_01 | AC | 353 ms
71,148 KB |
testcase_02 | AC | 330 ms
84,356 KB |
testcase_03 | AC | 331 ms
84,348 KB |
testcase_04 | AC | 325 ms
84,360 KB |
testcase_05 | AC | 323 ms
84,428 KB |
testcase_06 | AC | 327 ms
84,352 KB |
testcase_07 | AC | 343 ms
84,356 KB |
testcase_08 | AC | 344 ms
84,360 KB |
testcase_09 | AC | 346 ms
84,348 KB |
testcase_10 | AC | 344 ms
84,348 KB |
testcase_11 | AC | 347 ms
84,352 KB |
testcase_12 | AC | 349 ms
84,356 KB |
testcase_13 | AC | 349 ms
84,352 KB |
testcase_14 | AC | 354 ms
84,344 KB |
testcase_15 | AC | 350 ms
84,352 KB |
testcase_16 | AC | 344 ms
84,352 KB |
testcase_17 | AC | 304 ms
84,076 KB |
testcase_18 | AC | 303 ms
84,084 KB |
testcase_19 | AC | 303 ms
84,084 KB |
testcase_20 | AC | 349 ms
71,144 KB |
testcase_21 | AC | 345 ms
84,356 KB |
testcase_22 | AC | 342 ms
84,352 KB |
testcase_23 | AC | 347 ms
84,352 KB |
testcase_24 | AC | 345 ms
84,348 KB |
testcase_25 | AC | 343 ms
84,352 KB |
testcase_26 | AC | 347 ms
84,352 KB |
testcase_27 | AC | 326 ms
84,344 KB |
testcase_28 | AC | 350 ms
84,348 KB |
testcase_29 | AC | 343 ms
84,356 KB |
testcase_30 | AC | 342 ms
84,356 KB |
testcase_31 | AC | 343 ms
84,352 KB |
testcase_32 | AC | 328 ms
84,348 KB |
testcase_33 | AC | 345 ms
84,352 KB |
testcase_34 | AC | 350 ms
84,348 KB |
testcase_35 | AC | 349 ms
84,356 KB |
testcase_36 | AC | 343 ms
84,352 KB |
testcase_37 | AC | 350 ms
84,356 KB |
testcase_38 | AC | 346 ms
84,352 KB |
testcase_39 | AC | 352 ms
84,352 KB |
testcase_40 | AC | 304 ms
84,020 KB |
testcase_41 | AC | 301 ms
84,084 KB |
testcase_42 | AC | 351 ms
84,356 KB |
testcase_43 | AC | 353 ms
84,356 KB |
ソースコード
package main.java.yukicoder; import java.util.Scanner; import java.util.ArrayList; import java.util.List; import java.util.Arrays; public class C { public static void main(String[] args) { int maxNumber = 10000000; // ステップ1:「2から上限値までの整数」を探索リストに入れる。 boolean[] targetNumbers = new boolean[maxNumber + 1]; Arrays.fill(targetNumbers, true); targetNumbers[0] = false; targetNumbers[1] = false; // 素数リスト List<Integer> primeNumbers = new ArrayList<Integer>(); int sqrt = (int) Math.sqrt(maxNumber); // ステップ3:探索リストの先頭の値が、引数の平方根に達するまでふるい落とし操作を続ける。 for(int i=2; i<=sqrt; i++) { // ステップ2:探索リストの先頭の数を素数とし、その倍数を探索リストから篩い落とす。 // ※この時、既に篩い落とされた数(false)は除外する。 int firstNum = i; if (targetNumbers[i]) { for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) { targetNumbers[j] = false; } } } // ステップ4:探索リストに残った値を素数リストに移して処理終了。 for (int i=2; i<targetNumbers.length; i++) { if (targetNumbers[i]) { primeNumbers.add(i); } } //System.out.println(); Scanner scanner = new Scanner(System.in); double n = Double.parseDouble(scanner.next()); //double n = 500000; int ans = 0; int size = primeNumbers.size(); for(int r=0; r<size; r++) { Integer rval = primeNumbers.get(r); if(rval > n) break; int ival = (int)Math.pow(rval, 2); for(int p=0; p<size; p++) { Integer pval = primeNumbers.get(p); if(ival-pval > size || ival-pval < 0) break; if(pval > n || ival-pval > n) continue; if(targetNumbers[ival-pval]) ans++; } } System.out.println(ans); scanner.close(); } }