博客

蓝桥杯2019决赛 质数拆分

【题目描述】

将 20192019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 2 + 2017 = 2019与 2017 + 2 = 2019 视为同一种方法。

【答案提交】

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

个人答案：55965365465060

测试网址

：

https://www.lanqiao.cn/problems/809/learning/

个人解法

【解法一】

思路解析：（暂未做思路解析，有需要再补）

public class _质数拆分 {
	static int[] arr;
	static int cnt = 0;

	public static void main(String[] args) {
		int n = 2019;
		ouLaShai(n);
		long[] dp = new long[n + 1];
		dp[0] = 1;
		for(int j=cnt; j>=1; --j) {
			for(int i=n; i>=arr[j]; --i) {
				dp[i] += dp[i-arr[j]];
			}
		}
		System.out.println(dp[n]);
	}

	/**
	 * 	欧拉筛（质数的线性筛选法），比埃式筛效率更高、速度更快
	 * @param n
	 */
	public static void ouLaShai(int n) {
		arr = new int[n + 1];
		boolean[] pin = new boolean[n + 1];
		for (int i = 2; i <= n; ++i) {
			if (!pin[i])
				arr[++cnt] = i;
			for (int j = 1; j <= cnt && arr[j] * i <= n; ++j) {
				pin[arr[j] * i] = true;
				if (i % arr[j] == 0)
					break;
			}
		}
	}
}