题目要求：
kotor拿到了一些正整数。 她决定从每个正整数取出一个素因子。但是, kotori有强迫症， 她不允许两个不同的正整数取出相同的素因子。她想知道，最终所有取出的数的和的最小值是多少?
注:若a mod k== 0,则称k是a的因子。若一个数有且仅有两个因子,则称其是素数。显然1只有一个因子,不是素数。
输入：12 15 28 22
输出：17
分析：
数字12分解得到质因数：2 2 3， 有效质因数：2 3
数字15分解得到质因数：3 5 有效质因数：3 5
数字28分解得到质因数：2 2 7 有效质因数：2 7
数字12分解得到质因数：2 11 有效质因数：2 11
转换成矩阵得到（第一列是质因数升序排列，第一排是输入的数字）：
. 12 15 22 28
2 1 0 1 1
3 1 1 0 0
5 0 1 0 0
7 0 0 0 1
11 0 0 1 0
从上矩阵发现规律，列数为4，行数为5，而案例给的17正好等于2+3+5+7。
即答案规则类似于如下：
行数>=列数 取前(列数)行的质因数相加即可。
行数<列数 则无法分配质因数，提示“错误”。
另外假设现给 12 24 13，则得到以下矩阵
12 24 13
2 1 1 0
3 1 1 0
13 0 0 1
验证通过
但是如果再变一下用户输入的数据 12 13，则得到以下矩阵
12 13
2 1 0
3 1 0
13 0 1
此时发现验证不通过，根据规则，取前两行质因数，程序输出得到5，但是实际需要2+13=15。
所以根据此时分析得到，我们在生成质因数矩阵表的时候需要排除用户输入的质因数数字，单独把该质因数数字最后拿来相加，即优化后得到的矩阵表为：
12
2 1
3 1
得到质因数2，再加上用户输入的质因数13，即得到15.
下面是代码，proc2是简易版【易懂的】，【proc3】是同原理优化版，纯算法。
import java.util.*;
public class Test06 {
static boolean DEBUG=false;
public static Integer proc2(int[] nums){
//int[][] map=new int[1000][nums.length];
List<Integer> keyList=new LinkedList();//质数列
boolean[] ket_exists=new boolean[1000];
boolean[] n2=new boolean[1000];//获得质数表
int c=0;
//通过取反来获得质数表
for (int i = 2; i < 500; i++)
for (int j = 2; j < (1000/i)+1; j++) {
int k1=i*j;
if(k1>=1000)break;
n2[k1]=true;
c++;
}
for (int i=2;i<1000;i++)if(!n2[i])keyList.add(i);
List<Integer> kTable=new LinkedList();//合数表
List<Integer> zTable=new LinkedList();//输入数字的质数表
// 分离质数合数，因为质数只有1和他本身，它本身就是质数，就没有比较加入后续的计算。
for (int i = 0; i < nums.length; i++) {
int num_t=nums[i];
if (keyList.contains(num_t)){
zTable.add(num_t); //加入质数表
nums[i]=0;
}else{
kTable.add(num_t); //加入合数表
}
}
//重置一下用户输入的数列，默认后面都只处理合数的数列
if(kTable.size()>0){
Arrays.sort(nums); //排个序。
nums=Arrays.copyOfRange(nums,zTable.size(),nums.length);//清除上面标记为0得记录
}else{
nums=new int[0]; //用户全给的质数数列，没有合数。。。
}
int max_offset_h=0; //最大因数质数的大小，后面会有用。
//放到表里
for (int num : nums) {
int tn = num; //取出数字，保证不会影响序列里面的。
for (int x : keyList) {
if (tn == 1) break; //只剩1了，跳出循环
if (tn % x != 0) continue; //无法整除，不是因数，跳到下一循环
if (x > tn) break; //除数比被除数大了，跳出循环，很有概率程序出现问题了【不在范围内】
if (!ket_exists[x]) ket_exists[x] = true; //当该质数因数没有用过，就标记一下，该质数入库了。
if (max_offset_h < x) max_offset_h = x; //标记一下使用最大的因数数字是多少
do {
tn = tn / x; //做除法
} while (tn % x == 0); //如果下一阶段还能除，则继续除。
}
}
//如果二维表的行数>列数，则只取前[列数]个行的质因数。
//如果二维表的行数=列数，直接加完就行。
//如果二维表的行数<列数，那么质因数个数肯定不够用，则报异常。
int table_height_max=0; //定义当前记录的行数【也就是因数个数】
int sum_k=0; //定义结果记录值
for(int k:keyList){ //循环一下质数队列
if(ket_exists[k])table_height_max+=1; //如果
if(k>max_offset_h) break; //如果超出上面记录的最大的质因数，就跳出
if(table_height_max<=nums.length)sum_k+=k; //如果当前行的行号小于或等于列数，则把值加入。
}
if(table_height_max<nums.length){ //如果表的总行数小于合数的个数，就异常。
if(DEBUG)System.out.println("proc2无法计算");
return null;
}
if(zTable.size()>0) for (int n:zTable) {
sum_k+=n;
}
if(DEBUG)System.out.println("proc2值为:"+sum_k);
return sum_k;
}
public static Integer proc3(int[] nums){
Set<Integer> ket_exists=new TreeSet();
List<Integer> zTable=new LinkedList();//输入数字的质数表
int max_offset_h=0; //最大因数质数的大小，后面会有用。
//分析数据，并放到表里。
for (int num : nums) {
int tn = num; //取出数字，保证不会影响序列里面的。
for (int x = 2; x <= Math.sqrt(tn); x++) {
if (tn == 1) break; //只剩1了，跳出循环
if (tn % x != 0) continue; //无法整除，不是因数，跳到下一循环
if (x > tn) break; //除数比被除数大了，跳出循环，很有概率程序出现问题了【不在范围内】
ket_exists.add(x); //该质数入库了。
if (max_offset_h < x) max_offset_h = x; //标记一下使用最大的因数数字是多少
do {
tn = tn / x; //做除法
} while (tn % x == 0); //如果下一阶段还能除，则继续除。
}
if(tn==num) {
zTable.add(num);
continue;} // 分离质数合数，因为质数只有1和他本身，它本身就是质数，就没有比较加入后续的计算。
if(tn==1)continue;
ket_exists.add(tn);
}
int sum_k=0,i=0;
for (int k:ket_exists)if(i<nums.length-zTable.size()){ sum_k+=k;i++;} //最终的统计结果。
if(ket_exists.size()<nums.length-zTable.size()){ //如果表的总行数【质因数】小于合数【用户输入的数字组的合数】的个数，就异常。
if(DEBUG)System.out.println("proc3：无法计算。");
return null;
}
if(zTable.size()>0) for (int n:zTable) sum_k+=n; // 用户输入的质数数字直接加入就行。
if(DEBUG)System.out.println("proc3值为:"+sum_k); //输出
return sum_k;
}
public static void main(String[] args) {
int[][] testData= new int[][]{
new int[]{12,15,28,22},
new int[]{12,15,25,13},
new int[]{12,15,28,13},
new int[]{10,15,28,8,20},
};
Integer[] result=new Integer[]{17,23,23,null};
System.out.println("基础正确性测试");
for (int i = 0; i < testData.length; i++) {
if(Objects.equals(proc2(Arrays.copyOf(testData[i],testData[i].length)), result[i])){ System.out.println("proc2测试通过"); }
if(Objects.equals(proc3(Arrays.copyOf(testData[i],testData[i].length)), result[i])){ System.out.println("proc3测试通过"); }
}
int count=10000;
long time=System.currentTimeMillis();
for (int j = 0; j < count; j++) {
for (int[] testDatum : testData) {
proc2(Arrays.copyOf(testDatum, testDatum.length));
}
}
long time2=System.currentTimeMillis();
System.out.println("proc2 "+count+"次测试:"+(time2-time)+"ms");
for (int j = 0; j < count; j++) {
for (int[] testDatum : testData) {
proc3(Arrays.copyOf(testDatum, testDatum.length));
}
}
long time3=System.currentTimeMillis();
System.out.println("proc3 "+count+"次测试:"+(time3-time2)+"ms");
count=1000000;
for (int j = 0; j < count; j++) {
for (int[] testDatum : testData) {
proc3(Arrays.copyOf(testDatum, testDatum.length));
}
}
long time4=System.currentTimeMillis();
System.out.println("proc3 "+count+"次测试:"+(time4-time3)+"ms");
}
public static void input(){
Scanner sc=new Scanner(System.in);
System.out.println("等待输入");
int count=sc.nextInt();
System.out.println("个数:"+count);
int[] nums=new int[count];
for (int i = 0; i < count; i++) nums[i]=sc.nextInt();
proc3(nums);
}
}