數論問題

問題：給定一個數值，判斷他是否等于一連串素數之和（這些素數必須是連續的）。輸出滿足條件的組合的個數。

題解：預先求出連續的素數和。然後找到不大于n的最大素數，那麼所有的組合（連續不斷的素數）隻可能在此範圍内。

一些正整數可以通過和一個或多個連續的素數表示。有多少這樣的陳述是一個給定的正整數嗎？例如，整數53有兩種表示方法5 + 7 + 11 + 13 + 17和53。整數41有三表示2 + 3 + 5 + 7 + 11 + 13，11 + 13 + 17，和41。整數3隻有一個表示，這是3。整數20則沒有這樣的表現。注意，必須連續素數因子數，是以無論是7 + 13和3 + 5 + 5 + 7是整數20有效的表示。

Sample Input

2

3

17

41

20

666

12

53

Sample Output

1

1

2

3

1

2

回答：

    #include <cstring>  

    #include <iostream>  

    using namespace std;  

    bool flag[10002];  

    int prime[10002], sum[1402];  

    int Pnum;  

    int main()  

    {  

        int i, j, k ;  

        memset(flag,-1,sizeof(flag));  

        memset(sum,0,sizeof(sum));  

        memset(prime,0,sizeof(prime));  

        Pnum = 0;  

        for ( i = 2; i <= 10000; i++ )  

        {  

            if ( flag[i] )  

            {  

                prime[++Pnum] = i;  

                for ( j = 2; i*j <= 10000; j++ )  

                    flag[i*j] = 0;  

            }  

        }  

        for ( i = 1; i <= Pnum; i++ )  

            sum[i] = sum[i-1] + prime[i];  

        int n, cnt;  

        while ( cin >> n && n )  

        {  

            cnt = i = 0;  

            while ( prime[i] < n && i < Pnum ) i++;  

            if ( prime[i] == n ) cnt++;      

            for ( j = i - 1; j >= 1; j-- )  

            {  

                for ( k = 0; k < j; k++ )  

                    if ( sum[j] - sum[k] == n )  

                        cnt++;  

            }  

            cout << cnt << endl;  

        }  

        return 0;  

    } 

轉載于:https://www.cnblogs.com/benchao/p/4499969.html