车站建造问题

我用了一天时间，绞尽脑汁写出了AC的代码，满心欢喜去讨论区看看别人的思路，发现，这“哥德巴赫猜想”什么鬼？！！！！！！非素数可分解为两个或三个素数！！！！喂喂喂，裁判，这有人作弊！！！！
好吧，冷静下来，一研究，满嘴苦涩，我这是绕了个大弯啊！！！
这里先解释下“哥德巴赫猜想”，有兴趣的可以看看后面的我的非“哥德巴赫猜想”解法。
“哥德巴赫猜想”：任一大于2的偶数都可写成两个素数之和。还有，任一大于5的整数都可写成三个质数之和。
由此，可以知道：
1.两个站之间的距离 D 如果是素数，那站数+1；
2.D 不是素数，但它是偶数，那站数+2就可以了；
3.D 不是素数，是奇数。因为奇数=奇数+偶数，而2是唯一一个是偶数的素数，所以，如果D-2是素数的话，站数+2，否则+3；
4.最后，别忘了，始发站也算一站，把它加上，就是答案。
代码如下：

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    //我用了两个哈希set保存素数和非素数，不用也能过,而且更快，内存也没有更大
    public static HashSet<Integer> primes;
    public static HashSet<Integer> noprimes;

    public int work (int n, int[] a) {
        // write code here
        primes=new HashSet<Integer>();
        noprimes=new HashSet<Integer>();
        primes.add(1);
        int count=1;
        for(int i=0;i<n-1;i++){
            int all=a[i+1]-a[i];
            if(isPrime(all)){
                count++;
            }else{
                if(all%2==0){
                    count+=2;
                }else{
                    if(isPrime(all-2)){
                        count+=2;
                    }else{
                        count+=3;
                    }
                }
            }
        }
        return count;
    }

    public boolean isPrime(int n){ 
        if(primes.contains(n)){
            return true;
        }
        if(noprimes.contains(n)){
            return false;
        }
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0){
                noprimes.add(n);
                return false;
            }
        }
        primes.add(n);
        return true;
    }
}

我的非“哥德巴赫猜想”解法，耗时1607ms，内存254444K。

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */

    public static int[] primes;

    public int work (int n, int[] a) {
        // write code here
        //先把每段距离放到数组中，并得到最大的距离。
        int max=0;
        int[] distance=new int[n-1];
        for(int i=0;i<n-1;i++){
            distance[i]=a[i+1]-a[i];
            if(distance[i]>max){
                max=distance[i];
            }
        }
        //然后求出max以内的所有素数
        //素数标0，非素数标上前一个素数的位置，这样遇到非素数可以快速地找到下一个素数
        //素数的倍数肯定不是素数，从小到大一遍历，就只剩下素数了。
        primes=new int[max+1];      //多分配一个元素，就是1对1,2对2，而不是0对1,1对2，盘逻辑的时候方便
        int pre=1;
        for(int i=2;i<=max/2;i++){
            if(primes[i]==0){
                for(int j=2;j<=max/i;j++){
                    primes[i*j]=-1;
                }
                pre=i;
            }else{
                primes[i]=pre;
            }
        }
        for(int i=max/2;i<=max;i++){
            if(primes[i]==0){
                pre=i;
            }else{
                primes[i]=pre;
            }
        }
        //这就是求最小数量，很简单
        int count=1;
        for(int i=0;i<n-1;i++){
            if(primes[distance[i]]==0){
                count++;
            }else{
                count+=getMin(distance[i]);
            }
        }
        return count;
    }

    public int getMin(int n){
        //先过一遍，如果能分解为两个素数最好了，直接返回2，顺便把素数都保存下来，下一步就省些事
        ArrayList<Integer> al=new ArrayList<Integer>();
        for(int i=n-1;i>=n/2;i--){
            if(primes[i]==0){
                if(primes[n-i]==0){
                    return 2;
                }else{
                    al.add(i);
                }
            }else{
                i=primes[i]+1;       //因为每轮循环结束后都有i--，所以+1抵消下
            }
        }
        //既然2不行，那最小的肯定是3，遇到3返回，遇不到只能先遍历着，最后返回最小值
        int min=n;
        for(int i=0;i<al.size();i++){
            int a=getMin(n-al.get(i))+1;
            if(a==3){
                return 3;
            }else if(a<min){
                min=a;
            }
        }
        return min;
    }
}