主要分析:
(1):将2019拆分成三个素数平方和,就要先得到三个素数,这也就涉及到了三个素数的范围,我们不妨从其中最大的质数推论,因为是三个素数的平方和,所以最大的素数必然小于 ,现在也就了解了三个素数的大致范围,那么也就可以将这个范围内的素数放进数组中操作;
(2):其次,三个素数可能有多种组合方式,可以利用到三重循环遍历所有情况,但也因为组合的多样,最后结果可能重复出现,因此要去重,例:(7、11、43)和(11、7、43),可以发现,这两对质数,虽然顺序不一,但表达的却是同一种结果,那发生这种情况又该如何去重呢?这里可以采用一个小技巧:排序
实例代码
package net.algchallenge; import java.util.Arrays; public class Split2019 { public static void mAIn(String[] args) { final int N = (int) Math.sqrt(2019);//定义常量N限制素数的范围 int[] primeArr = new int[N];//定义primeArr数组用于保存质数 int count = -1; Integer[][] arr = new Integer[N][3];//定义二维数组arr保存最后要输出的质数数组 for (int i = 2; i <= N; i++) { boolean flag = false; for (int j = 2; j <= Math.sqrt(i); j++) { if (i % j == 0) { flag = true; break; } } if (!flag) { count++; primeArr[count] = i; } } int count2 = -1; for (int i = 0; i <= N - 1; i++) { for (int j = 0; j <= N - 1; j++) { for (int x = 0; x <= N - 1; x++) { if (primeArr[i] * primeArr[i] + primeArr[j] * primeArr[j] + primeArr[x] * primeArr[x] == 2019) { Integer[] tempArr = {primeArr[i], primeArr[j], primeArr[x]};//将符合上面if条件的质数保存在tempArr数组中 Arrays.sort(tempArr);//排序,以便去重 boolean ifContain = false;//检测arr数组中是否存在该tempArr数组 for (int y = 0; y <= N - 1; y++){ if (Arrays.equals(arr[y], tempArr)){ ifContain = true; break; } } if (!ifContain) {//arr数组中不存在该tempArr数组才放进arr数组中 count2++; arr[count2] = tempArr; break; } } } } } Integer[] nullArr = {null, null, null};//因为前面二维数组长度为N,但是不可能全部装满,剩下的数组中自然是null //因此定义nullArr数组用于筛选结果 for (int i = 0; i <= N - 1; i++) { if (!Arrays.equals(arr[i], nullArr)) { System.out.println(String.format("2019 = %d^2 + %d^2 + %d^2", arr[i][0], arr[i][1], arr[i][2])); } } } }
结果: