车站建造问题

解题思路

根据题意，车站数最少是n，如果相邻两个车站的距离不是1或素数，就需要在中间插入一个或多个车站来使每个车站之间的距离都是1或素数，也就是求把一个非素数分解为素数的个数，可以想到哥德巴赫猜想。

维基百科：哥德巴赫猜想

对每个车站之间的距离进行判断，如果不是1或素数，就需要进行分解。如果距离是偶数，那么最多只需要新增一个车站；如果是奇数，最多需要新增两个车站，但也有只需要新增一个车站的例子，比如9=2+7和15=2+13。如果想把一个奇数分解为两个素数，就必须是一个奇素数、一个偶素数，偶素数只有2，所以先判断一下-2之后能不能得到素数，如果能，只需要新增1个车站；如果不能，那么由哥德巴赫猜想，-2之后的奇数也一定能分解成2个素数，所以需要新增 2个车站。

AC代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int work(int n, int* a, int aLen) {
        int count = n;
        for (int i = 1; i < n; i++) {
            int dist = a[i] - a[i - 1];
            if (dist != 1 && !isprime(dist)) {
                if (dist % 2 == 0 || isprime(dist - 2))
                    count += 1;
                else
                    count += 2;
            }
        }
        return count;
    }
private:
    bool isprime(int n) {
        if (n == 1)
            return false;
        for (int i = 2; i * i <= n; i++)
            if (n % i == 0)
                return false;
        return true;
    }
};

这题居然用到了哥德巴赫猜想，真的秀到我了！
讲讲思路吧，首先每个牛牛所在村庄都要建一座车站，我们就将结果ret初始化为牛牛村庄的数量aLen。接下来就是计算每两个牛牛村庄之间的距离，如果为质数（或称素数），则不用在这两个村庄之间再修建车站；如果为非质数，就要分几种情况进行讨论（不妨设某两个村庄距离为为len）：

1. len为偶数，则可拆非为两个质数之和，意思就是在这两个村庄之间再修一座车站，ret++即可；
2. len为奇数，则将将len拆分为len = (len - 2) + len，此时对于len-2，需要再分两种情况讨论：
   （i）len-2为质数，则len就是len-2和2两个质数之和，意思就是在这两个村庄之间再修一座车站，ret++即可；
   （ii）len-2为非质数，则可将len-2拆分成2个质数之和，进一步可将len拆分为3个质数之和，意思就是在这两个村庄之间再修两座车站，ret+=2即可。
   至于为什么会得到上面的结论，就请自行百度哥德巴赫猜想吧！QAQ
   代码就自己写吧，我的代码没有经过优化，就不放上来献丑了^^。

//一开始使用贪心，错误，看了题解后才使用哥德巴赫猜想
class Solution {
private:
	int res;
public:
	int work(int n, int* a, int aLen) {
		res = 1;
		for (int i = 1; i < aLen; i++)
		{
			int distance = a[i] - a[i - 1];
			if (is_prime(distance))
				res++;
			else
			{
				if (distance % 2 == 0)
					res += 2;
				else
				{
					if (is_prime(distance - 2))
						res += 2;
					else
						res += 3;
				}
			}
		}
		return res;
	}

	bool is_prime(int n)
	{
		for (int i = 2; i <= sqrt(n); i++)
			if (n % i == 0)
				return false;
		return true;
	}
};

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    isPrime(int x){
        for(int i=2;i*i<=n;i++)
            if(x%i==0)
                return false;
        return true;
    }
    int work(int n, int* a, int aLen) {
        int cnt = 1, d;
        for(int i=1;i<n;i++){
            d = a[i] - a[i-1];
            if(isPrime(d))
                cnt++;
            else{
                if(d&1){
                    if(isPrime(d-2))
                        cnt += 2;
                    else
                        cnt += 3;
                }else
                    cnt += 2;
            }
        }
        return cnt;
    }
};

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int work (int n, int[] a) {
        int count = 1,len = 0;
        for(int i=1; i<a.length; i++) {
            len = a[i] - a[i-1];
            if(isPrime(len)) {
                count++;
            } else if(len % 2 == 0 || isPrime(len-2)) {
                count += 2;
            } else {
                count += 3;
            }
        }
        return count;
    }
    
    private boolean isPrime(int num) {
        for(int i=2; i * i <= num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

1. 首先所有Ai均有车站，接下来判断距离是否为质数或1，是则车站数+1，否则继续判断距离；

2. 当距离为偶数时，可以表示为两个质数的和（根据哥德巴赫猜想）；

3. 当距离为奇数时，分解为p=(p-2)+2：

若p-2为质数，则可表示为两个质数的和
若p-2为非质数，则可表示为三个质数的和

class Solution:

    def work(self , n , a ):
        # write code here
        count = n
        dis = [(i-j)for i,j in zip(a[1:],a)]
        for i in dis:
            if( i!=1 and self.isPrimeNumber(i)==False):
                if(i%2==0 or self.isPrimeNumber(i-2)):
                    count+=1
                else:
                    count+=2
        return count

    def isPrimeNumber(self,x):
        flag = True
        if(x==1):
            flag = False
        for i in range(2,int(x)):
            if(x%i==0):
                flag=False
                break
        return flag

class Solution {
public:
    /**
    任一大于2的偶数都可写成两个质数（素数）之和
    任一大于5的整数都可写成三个质数（素数）之和

    首先建立n个车站（牛牛所在村庄）
    然后判断两个车站的距离dis是不是素数，
    如果是素数，两个车站之间不用再增加车站；
    如果dis不是素数，分两种情况（偶数和奇数）；
        如果dis是偶数（此时dis大于2），有任一大于2的偶数可以写成两个素数之和，所以在两个车站之间再增加一个车站即可；
        如果dis是奇数，奇数 = 奇数 + 偶数，。有任一大于5的整数都可写成三个质数（素数）之和，有2即是偶数又是素数，
            如果dis-2是素数，那么说明dis = 素数 + 2（素数），此时只用增加一座车站即可：n + 1;
            如果dis-2不是素数，有任一大于5的整数都可写成三个质数（素数）之和，知只要在两个车站之间建立两个车站即可：n + 2
    **/
    int isPrime(int number)
    {
        if (number==1||number==2)
        {
            return 1;
        }else
        {
            for (int i=2; i<=number/2; i++)
            {
                if(number % i == 0)
                {
                    return 0; //不是素数
                }
            }
        }

        return 1;  //是素数
    }
    /**
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int work(int n, int* a, int aLen) {
        // write code here
        for (int i=0; i<aLen-1; i++)
        {
            if (isPrime(a[i+1] - a[i])==1)
            {
                continue;
            }else
            {
                if((a[i+1] - a[i])%2 == 0)
                {
                    n += 1;
                }else
                {
                    if(isPrime(a[i+1] - a[i] - 2)==1)
                    {
                        n += 1;
                    }else
                    {
                        n += 2;
                    }
                }
            }
        }
        return n;
    }
};