結果
問題 |
No.8079 アルベド
|
ユーザー |
|
提出日時 | 2023-11-09 16:20:18 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,360 bytes |
コンパイル時間 | 2,501 ms |
コンパイル使用メモリ | 79,792 KB |
実行使用メモリ | 74,048 KB |
最終ジャッジ日時 | 2024-09-26 00:22:47 |
合計ジャッジ時間 | 20,400 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 6 TLE * 4 |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeMap<Integer , Integer> sums = new TreeMap<>(); for(int i = 0 ; i < n ; i++){ int num = sc.nextInt(); int cnt = constructPrimeNumbers(num , sums); System.out.println(cnt); sums.put(num , cnt); } } private static int constructPrimeNumbers(int maxNumber , TreeMap<Integer , Integer> sums) { int cnt = 0; int first = 2; if(sums.lowerEntry(maxNumber) != null){ Map.Entry<Integer , Integer> entry = sums.lowerEntry(maxNumber); cnt = entry.getValue(); first = entry.getKey(); } boolean[] targetNumbers = new boolean[maxNumber + 1]; Arrays.fill(targetNumbers, true); targetNumbers[0] = false; targetNumbers[1] = false; int sqrt = (int) Math.sqrt(maxNumber); for (int i = (int)Math.sqrt(first) ; i <= sqrt; i++) { int firstNum = i; if (targetNumbers[i]) { for (int j = i * firstNum; j < targetNumbers.length; j = j + firstNum) { targetNumbers[j] = false; } } } for (int i = first; i < targetNumbers.length; i++) { if (targetNumbers[i]) { cnt++; } } return cnt; } }