[AHOI2001] 质数和分解

import java.util.*;public class Main {static int[] ss = new int[201];public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNextInt()) {		int n = sc.nextInt();int num = 0; // 记录质数个数int[] dp = new int[201];dp[0] = 1;for (int i = 2; i <= n; i++) {if (is(i)) ss[++num] = i; // 计算好n前所有质数}for (int i = 1; i <= num; i++) {for (int j = ss[i]; j <= n; j++) { // 完全背包dp[j] += dp[j - ss[i]]; // 从当前素数开始，逐步计算更大的和}}System.out.println(dp[n]); // 得到和为n的组合数}}// 计算质数static boolean is(int x) {for (int i = 2; i <= x / 2; i++) {if (x % i == 0) return false;}return true;}
}

每日一水~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~