每日一道编程题（387）：西北大学上机题（五）

是不是超素数？

如果一个数是素数，并且能被分解为C（C>=2）个连续素数的和，则称这个数为“超素数”，请编程判断一个数是否是超素数。

输入格式：

一个正整数N（1

输出格式：

给定的整数N为超素数，请输入yes，否则请输出no

输入样例：

5

输出样例：

yes

解决方法：

（1）算法的基本思想：

（2）代码实现：

#include 
#include 
#define MAX_LENGTH 100000
using namespace std;

bool isPrimeNumber(int num);          //判断是否是素数
bool isSuperPrimeNumber(int num);     //判断是否是超素数
int sumOfArr(int *arr, int m, int n); //求数组arr从m到n的元素之和

int main(void)
{
    int num;
    cout <"请输入数字:"     cin >> num;
    if (isSuperPrimeNumber(num))
    {
        cout <"yes"     }
    else
    {
        cout <"no"     }
    return 0;
}

bool isPrimeNumber(int num)
{ //判断是否是素数
    if (num <= 1)
        return false;
    int result = true;
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            result = false;
            break;
        }
    }
    return result;
}

bool isSuperPrimeNumber(int num)
{
    //若num不是素数，返回false
    if (!isPrimeNumber(num))
        return false;
    bool result = true;
    int prime_arr[MAX_LENGTH]; //存放素数序列
    int length = 0;
    for (int i = 2; i     { //找出所有小于num的素数，存入prime_arr中
        if (isPrimeNumber(i))
        {
            prime_arr[length] = i;
            length++;
        }
    }
    int p, q; //定义两个工作指针，分别指向子序列的起始
    p = 0;
    q = length - 1;
    while (p     { //尝试找出和为num的子序列
        int sum = sumOfArr(prime_arr, p, q);
        if (sum         { //和小了，p后移
            p++;
        }
        else if (sum > num)
        { //和大了，q前移
            q--;
        }
        else
        { //找到了子序列
            break;
        }
    }
    if (p == q)
    { //检查是否是找到子序列而跳出循环的
        result = false;
    }
    else
    {
        //为了让结果更清楚，当是超素数时，输出具体的组合
        cout <"----- SUM OF -----"         for (int i = p; i <= q; i++)
        {
            cout <" ";
        }
        cout         cout <"------------------"     }
    return result;
}

int sumOfArr(int *arr, int m, int n)
{ //求数组arr从m到n的元素之和
    int sum = 0;
    for (int i = m; i <= n; i++)
    {
        sum += arr[i];
    }
    return sum;
}

输入格式：

输出格式：

输入样例：

fave cad ecd ygaijj

输出样例：

3