题解 | #车站建造问题#

题目：
X轴上 $10^{8}$ 个点，从左到右依次编号为0到 $10^{8}-1$ ，相邻点距离为1，其中有n个点有特殊意义，从小到大依次为 $a_{0}$ 到 $a_{n-1}$ ，其中保证 $a_{0}$ =0.
现在需要建设收集站，有两个要求必须被满足：
1、每个有意义的点必须修建收集站。
2、相邻收集站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设收集站的最小数量。
方法一：哥德巴赫猜想+欧拉筛选法构造素数表
站点数初始化为n,关键是要判断一个非素数可以分解成几个素数
这里就得用到哥德巴赫猜想：

一个数n是大于2的偶数时，最少可以分解为2个素数
一个数n是大于等于5的奇数时：如果n-2是素数，则n可以分解为最少2个素数
否则，n可以分解为最少3个素数

欧拉筛选法构造素数表：
构造一个从2到 $max(a[i]-a[i-1])$ 之间的素数表，具体如何构造呢？
从2开始到max，visit数组记录数是否已经被访问过，未访问过则加入素数表，再把prime里面记录的素数，升序来当做要消去合数的最小素因子，被消去的合数记录为被访问过，因为是用最小素因子来消去合数，为了避免重复消去合数，当 i是 $prime[j]$ 的倍数时， $i = k* prime[j]$ ，如果继续运算 $j+1，i * prime[j+1] = prime[j] * k*prime[j+1]$ ，这里 $prime[j]$ 是最小的素因子，当 $i = k * prime[j+1]$ 时会重复消去 $k*prime[j+1]*prime[j]$ ，所以才跳出循环。
举个例子： $i = 4 ，prime[0] = 2$ ，如果不跳出循环， $prime[1] = 3，i*prime[1]=4 * 3 = 12$ ，在 $i = 6$ 时会计算 $i*prime[0]=12$ ,这样就会造成重复计算，欧拉筛法的原理是通过最小素因子来消除。
、
图片说明

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    ArrayList<Integer>prime=new ArrayList<>();
    public int work (int n, int[] a) {
        // write code here
        if(n==1)return 1;
        int max=0;
        int[]diff=new int[n];
        for(int i=1;i<n;i++){
            max=Math.max(max,a[i]-a[i-1]);
            diff[i]=a[i]-a[i-1];
        }
        Prime(max);//构造素数表
        int site=n;//每个有意义的点都可以建成收集站
        for(int i=1;i<n;i++){
            if(diff[i]<=3)continue;
            if(!prime.contains(diff[i])){
                if((diff[i]&1)==0)site+=1;//哥德巴赫猜想，大于2的偶数可以被拆成两个素数
                else {
                    if(prime.contains(diff[i]-2))site+=1;
                    else site+=2;
                }
            }
        }
        return site;
    }
    //欧拉筛选法选素数
    void Prime(int max){
        boolean[]visit=new boolean[max+1];//记录数是否被访问过
        for(int i=2;i<=max;i++){
            if(!visit[i]){
                prime.add(i);//设所有数都为素数
            }
            for(int j=0;j<prime.size()&&i*prime.get(j)<=max;j++){
                visit[i*prime.get(j)]=true;//把prime里面记录的素数，升序来当做要消去合数的最小素因子
                if(i%prime.get(j)==0)
                    break;
            }
        }
    }
}

复杂度：
时间复杂度：构造素数表的时间复杂度为 $O(m)$ ,主函数一层循环, $O(n)$ ,因此时间复杂度为 $O(mn)$
空间复杂度：素数表的大小不超过 $max(a[i]-a[i-1])$ ,因此空间复杂度为 $O(m)$
( $m=max(a[i]-a[i-1])$ )
方法二:哥德巴赫猜想+判断素数
直接判断每个数x是否是素数会更快，素数的定义就是这个数除了1和它本身没有别的因数，那么可以判断从2到x-1,是否有x的因数，但是这样效率很低，其实一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(x)，一个大于等于sqrt(x)，据此，并不需要遍历到x-1，遍历到sqrt(x)即可，因为若sqrt(x)左侧找不到约数，那么右侧也一定找不到约数。

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int work (int n, int[] a) {
        // write code here
        if(n==1)return 1;
        int site=n;//每个有意义的点都可以建成收集站
        for(int i=1;i<n;i++){
            int diff=a[i]-a[i-1];
            if(diff<=3)continue;
            else if(!isPrime(diff)){//哥德巴赫猜想，大于2的偶数可以被拆成两个素数
                if((diff&1)==0)site+=1;
                else{
                     if(isPrime(diff-2))site+=1;//奇数减2如果是素数则可以拆成一个素数和2
                     else site+=2;}//否则可以拆成3个素数
            }
        }
        return site;
    }
    //判断是否是素数
    boolean isPrime(int x){
       for(int i=2;i*i<=x;i++)
           if(x%i==0)return false;
        return true;
    }
}

复杂度：
时间复杂度：isPrime()函数的时间复杂度为 $图片说明$ ,因此总的时间复杂度为 $图片说明$
空间复杂度： $O(1)$ ,额外变量的空间复杂度为常数级
( $m=max(a[i]-a[i-1])$ )