题意概述

• 对数轴上的n个点，必须建立收集站
• 相邻两收集站的距离若不为素数或1，则在其中间尽量少的建立若干收集站使其满足条件
• 欲求解最少建立收集站的个数

方法一：哥德巴赫猜想

思路与具体做法

哥德巴赫猜想——引自百度百科
“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”：任一大于2的偶数都可写成两个素数之和
“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”：任一个大于7的奇数都能被表示成三个奇质数的和

• 若两站之间距离为素数或1：
  • 则两站间不需修站
• 若两站之间距离为偶合数：
  • 根据强哥德巴赫猜想，大于2的偶数距离间都不需要修建（小于等于2的偶数只有2，为素数）
• 若两站之间距离为奇合数：
  • 因为奇数只可以拆分成奇数+偶数，现在要求拆分出的这两段子距离也都是素数，而2是唯一的偶数的素数，所以此时若拆分出来的奇数也是素数，则两站间最少修建一个站台
  • 若不满足上述情况，根据弱哥德巴赫猜想，大于7的奇数距离都至少能被拆分成3个奇质数，（小于等于7的奇数满足素数或1的情况）

class Solution {
public:
    bool isprime(int n){
        if(n==1)return true;//判断1 
        for(int i=2;i*i<=n;i++){//判断素数 
            if(n%i==0)return false;
        }
        return true;
    }
    int work(int n, int* a, int aLen){
        int ans=1;//第一个站一定要建 
        for(int i=1;i<n;i++){//从第二个站开始遍历 
            int distance=a[i]-a[i-1];
            if(isprime(distance))ans++;//两站距离为素数，则直接建立该站，两站间不需再建站 
            else{//两站距离为合数
                if(distance%2==0)ans+=2;//偶合数，强哥德巴赫猜想 
                else{//奇合数 
                    if(isprime(distance-2))ans+=2;//奇数=奇数+偶数，拆分 
                    else  ans+=3;//弱哥德巴赫猜想            
                }
            }
        } 
        return ans;
    }
};

时间复杂度和空间复杂度分析

时间复杂度： ， n为点数，为一次判断素数的最大时间复杂度
空间复杂度： ，仅用到了一个整形变量ans用于记录车站数量

方法二：动态规划（超时）

思路与具体做法

• dp[i]:长度为i的距离内可新建的站数目
• 首先计算题目中已给的两站间最大距离
• 接着枚举所有站间距离，直到站间最大距离
• 对每一个站间距离
  • 为素数，说明这段站间距离i不需要新建站
  • 为合数，则对这段站间距离i进行转态转移
• 转态转移：
  • 从距离1开始枚举站间距离的所有素数j，对站间距i，
    • 若它不进行分割，站间距离i不变，可新建的站数目不变，
    • 若它可进行分割，站间距离i减少j，可新建的站数目加1，
• 注意：
  • 因为需要枚举一段距离内的所有素数，所以这里会超时，即使用欧拉筛法进行打表，得到一个素数表，也会出现运行超时的情况

class Solution {
public:
    int pNum=0;//素数个数
    void Find_Prime2(int maxn,int p[],int prime[]){
        for(int i=2;i<maxn;i++){    
            if(p[i]==false){ 
                prime[pNum++]=i;
            } 
            for(int j=0;j<pNum&&i*prime[j]<maxn;j++){//遍历每一个已找到的素数
                p[i*prime[j]]=true;//这个素数的倍数是合数
                if(i%prime[j]==0)break;//因为每个数只被它的最小质因子筛一次，在此之后的质数不用筛
            } 
        } 
    }
    int work(int n, int* a, int aLen) {
        int maxx=1;//两站间的最大距离 
        for(int i=1;i<n;i++){
            maxx=max(maxx,a[i]-a[i-1]);
        } 
        int p[maxx+1];//初始都是素数
        memset(p,0,sizeof(p));
        int prime[maxx+1];//素数表        
        Find_Prime2(maxx+1,p,prime);//打表，表长为两点之间最长距离 
        int dp[maxx+1];//两站需建多少站点 
        for(int i=1;i<=maxx;i++){
            if(!p[i]||i==1){//距离为素数，中间不用建站 
                dp[i]=0;
            }else{//距离不为素数 
                dp[i]=0x3fffffff;
                for(int j=1;j<=i;j++){
                    if(!p[j]){
                        dp[i]=min(dp[i],dp[i-j]+1);
                    }
                }
            }
        }
        int ans=n;
        for(int i=1;i<n;i++){
            ans+=dp[a[i]-a[i-1]];
        }
        return ans;
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，d为站间最大距离，dp数组求解两层循环
空间复杂度：，d为站间最大距离，这里仅用到了一个长度为d+1的dp数组