把一个正整数分解成3个质数,如果可以 打印该数 和3个质数 不可以就return 错误信息;
求正解……
------解决方案--------------------
for example
- Java code
import java.util.*;public class Test { public static void main(String[] args) throws Throwable { int n = 1000; //测试1000以内的数据 for (int i=3; i<n; i++) { findPn(i, 3); } } public static void findPn(int n, int count) throws Exception { //把n分解为count个质数的和 if (n <= 0 || count <= 0 || count > n) { //非法数据的时候,异常退出 throw new Exception("no result"); } if (count == n) { //n和count相同的时候,n就是count个1相加 System.out.printf("%d=1", n); for (int i=1; i<count; i++) { System.out.printf("+%d", 1); } System.out.println(); return; } int[] num = new int[count-1]; //声明一个count-1个元素的数组,用于保存分解的结果 Arrays.fill(num, 1);//初始化数组每个元素为1 int remain = n; //定义一个变量用于保存分解成count-1个数以后还剩下的值 boolean found = true; //定义一个变量用于判断分解的数是否都是质数 while (num[0] < n - count + 1) { //循环遍历拆分n为count个数的和 found = true; remain = n; for (int i=0; i<num.length; i++) { //拆分保存到数组中的元素是否都是质数 found &= isPn(num[i]); if (! found) break; remain -= num[i]; //拆分到数组后剩余的数 } found &= isPn(remain);//判断剩余的数是否都是质数 if (found) { //如果拆分的结果都是质数 System.out.printf("%d=%d", n, num[0]); for (int i=1; i<num.length; i++) { System.out.printf("+%d", num[i]); } System.out.printf("+%d\n", remain); return; //找到一组结果就退出 } num[num.length-1]++; //数组元素分配调整,最后一个元素加1 remain = 1; //设定剩余值为1,就是保证必须要有剩余值,否则不能满足count个数之和(因为数组是count-1个) for (int i=num.length-1, sum=0; i>0; i--, sum=0) { for (int j=0; j<i; j++) { //求出每个数组元素位置之前的元素的和 sum += num[j]; } if (num[i] == n - sum + remain) { //判断数组元素分配是否达到最大 num[i] = 1; //如果达到最大,则重新分配数组元素为1 num[i-1]++; //数组元素位置的前一个位置的元素加1 } remain += num[i]; //调整剩余值 } } throw new Exception("no result"); //如果找不到结果就抛出异常 } public static boolean isPn(int n) { //判断一个数是否是质数 if (n <= 0) return false; //如果小于等于0,不是质数 else if (n < 4) return true; //小于4,也就是1到3都是质数 for (int i=2; i<=(int)(Math.sqrt(n)); i++) { //判断除了1和本身之外是否有因数 if (n%i == 0) return false; //有则不是质数 } return true;//没有则是质数 }}