蓝桥杯算法提高VIP-拿糖果-题解(Java代码)java开荒者

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int primesSum = (int)(Math.sqrt(n));
        boolean[] primes = new boolean[primesSum+1];
        for(int i = 2 ; i <= primesSum / i ; i++)
            if(!primes[i])
                for(int j = i ; j <= primesSum / i ; j++)
                    primes[i*j] = true;
        //以上使用埃拉托色尼算法求2-√n之间的素数
        int max = 0;
        int[] candy = new int[n+1];
        for(int i = 2 ; i <= primesSum ; i++)
            if(!primes[i]) {
                max = i;
                candy[n-2*i] = i;
            }
            //第一个拿糖果的情况
        for(int i = n - 1 ; i >= 4 ; i--) {
            if(candy[i] != 0 && i >= 2) {    //只有当candy[i]不为0的时候，才是可能出现的糖果数，
                int sqrtC = (int)Math.sqrt(i);
                for(int j = 2 ; j <= sqrtC ; j++)
                    if(!primes[j] && i % j == 0)    //i为素数，且是j的因数时候，可以拿走
                        if(candy[i - 2*j] < candy[i] + j) {    //选取较优的方式
                            candy[i - 2*j] = candy[i] + j;
                            if(candy[i - 2*j] > max)
                                max = candy[i - 2*j];
                        }
            }
        }
        System.out.println(max);
    }
}