车站建设问题题解

【前言】
非常简单的数学题。

【正解】
问题可以拆分为许多子问题，子问题就是：给一个数m，将他拆分为尽可能少的若干个质数的和。
解题的关键就是哥德巴赫猜想。
对于质数，显然贡献就是1.
对于1，贡献也是1.
剩下的数分奇偶考虑，对于偶数，由哥德巴赫猜想，任意一个非2的偶数可以拆分为两个质数的和，所以偶数的贡献是2.
对于不是质数的奇数z，贡献只可能是2或3：
1、拆分为2个质数，必然为1奇1偶，分别为2和z-2，其中z-2为质数
2、拆分为3个质数，一种可行的拆分方法是拆分为一个奇质数和一个非2偶数，这个偶数根据哥德巴赫猜想可以拆分为两个质数。

贪心即可。

关于哥德巴赫猜想，虽然还没有被成功证明，但至少在我们现在所用到的数的范围内是没有反例的，所以可以大胆使用。

参考代码(非常简短)：

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