车站建造问题

描述
X轴上10^8个点，从左到右依次编号为0~10^8-1，相邻点距离为1，其中有n个点有特殊意义，从小到大依次为a0~an-1，其中保证a0=0.
现在需要建设收集站，有两个要求必须被满足：
1、每个有意义的点必须修建收集站。
2、相邻收集站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设收集站的最小数量。
示例
输入：3,[0,7,11]
返回值：4
说明：在0,7,8,11处建造收集站，差值分别为7,1,3，符合要求


方法一

思路分析

  本题需要用到数学的办法，相邻收集站的距离必须为1或者某个质数，因此循环遍历数组，如果数组相邻位置的距离不为质数，那么在这两个位置之间修建收集站，修建收集站的数量与两个位置的距离有关，设置这个距离为distance，那么分为以下两种情况：
如果distance为偶数，根据哥德巴赫猜想，大于2的偶数可以分为两个质数的和
如果distance为奇数，任何大于5的奇数都是三个质数的和
因此有以下步骤:
  • 首先设置修建收集站的个数count=n
  • 循环遍历数组，如果相邻位置的距离distance为质数不进行操作；
  • 如果distance不为质数，那么分为两种情况：
  • 如果distance为偶数，那么需要插入两个收集站，因此count+2
  • 如果distance为奇数，可将其拆分为：（distance-2）+2的形式，又可分为两种情况：
           1.（distance-2）如果为质数，则拆解为两个质数，因此count+2；
           2.（distance-2）如果不为质数，那么 将其拆分为(distance-1)+1，(distance-1)为偶数，偶数可分为两个质数的和，因此这种情况下需要修建三个收集站，即count+3
上面由于初始化设置count=n，因此在实际操作中插入两个收集站只需要加1，插入三个收集站只需要加2即可

图解



核心代码 

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int work(int n, int* a, int aLen) {
        // write code here
        int count=n;
        for(int i=0;i<n-1;i++)
        {
            int distance=a[i+1]-a[i];
            if(distance!=1&&prime(distance)==0)//distance不为质数，那么分为两种情况
            {
                if(distance%2==0||prime(distance-2)==1)//distance为偶数或者distance-2为质数，那么需要插入两个收集站，因此count+2
                    count++;
                else count=count+2;
            }
        }
        return count;
    }
    int prime(int n)//判断是否为素数
    {
      if (n == 1) 
      {
        return 0;
      }
    for(int i = 2; i*i <= n; i++)//只需要判断到平方根n即可
    {
        if (n % i == 0) 
        {
            return 0;
        }
    }
    return 1;
    }

};

复杂度分析

  • 时间复杂度：该方法的时间在于判断相邻位置的距离是否为质数，判断一个质数的时间复杂度为，需要遍历数组，因此总的时间复杂度为
  • 空间复杂度：空间复杂度为$O(1)$