結果
問題 | No.458 異なる素数の和 |
ユーザー |
![]() |
提出日時 | 2017-10-29 23:23:42 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 214 ms / 2,000 ms |
コード長 | 964 bytes |
コンパイル時間 | 2,221 ms |
コンパイル使用メモリ | 79,556 KB |
実行使用メモリ | 41,584 KB |
最終ジャッジ日時 | 2024-11-22 05:45:04 |
合計ジャッジ時間 | 8,062 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import java.math.BigDecimal;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.util.Scanner;import java.util.TreeSet;public class Main {public static long MOD = 1000000007;public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int N = sc.nextInt();boolean[] is_prime = new boolean[N + 1];Arrays.fill(is_prime, true);is_prime[0] = is_prime[1] = false;ArrayList<Integer> primes = new ArrayList<Integer>();for(int i = 2; i <= N; i++){if(!is_prime[i]){ continue; }primes.add(i);for(int j = i * 2; j <= N; j += i){is_prime[j] = false;}}int[] times = new int[N + 1];Arrays.fill(times, -1);times[0] = 0;for(final int p : primes){for(int v = N - p; v >= 0; v--){if(times[v] < 0){ continue; }times[v + p] = Math.max(times[v + p], times[v] + 1);}}System.out.println(times[N]);}}