网易8月8号笔试题-第一道题

import java.util.*;
public class Main {
    public static void main(String[] args) {
        //设置两组测试用例
        int[] a1 = {3, 5, 7}; //期待输出是6
        int[] a={1,1,1}; //期待输出是0
        int max = 0;
        //找出最大值
        for (int i : a)
            max = Math.max(max, i);
        //找出所有的素数
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (judgeSushu(i))
                list.add(i);
        }
        //这是一个动态规划
        int[] dp = new int[max + 1];
        dp[0] = 0;//这个是由其他转移过来的 dp[7-7]=dp[0]=1
        dp[1] = 0;
        //计算dp状态转移
        for (int i = 3; i <= max; i++)
        {
            for(int n:list)
            {
                if(n>i)
                    break;
                else
                    dp[i]=Math.max(dp[i],dp[i-n]+1);
            }
        }
        //统计数组中所有数的拆分成的最大素数个数
        int count=0;
        for(int i=0;i<a.length;i++)
            count+=dp[a[i]];
        System.out.println("总共有"+count+"个素数");
        
    }
    //判断一个数是否是素数
    public static boolean judgeSushu(int n)
    {
        for(int i=2;i<=Math.sqrt(n);i++)
            if(n%i==0)
            {
                return false;
            }
        return true;
    }


}