利用Java将2019拆分成三个素数平方和的方法实例

时间:2020-05-31 yeyu_xing 人气:2

主要分析：

（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]));
   }
  }
 }
}

结果：

总结

加载全部内容