采用这个思想，用如下循环完成对flag数组的设置。

       for(i=2;i<1000000;i++)      // 用筛法构建质数表

       {

        if (flag[i]=='1')

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

                            flag[j]='0';

    }

      （4）源程序2。

#include <iostream>

using namespace std;

int main()

{

    char flag[1000000];

       int i,j,n;

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

              flag[i]='1';

       for(i=2;i<1000000;i++)      // 用筛法构建质数表

       {

        if (flag[i]=='1')

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

                            flag[j]='0';

    }

    while(cin>>n&&n)

       {

       for(i=3;i<n;i++)

          {

          if(flag[i]=='1' && flag[n-i]=='1')

                {

             cout<<n<<" = "<<i<<" + "<<n-i<<endl;

             break;

                }

          }

       }

    return 0;

}

      将源程序1和2分别提交给POJ评判系统，可得到如图1所示的评判结果。从结果可以看出，源程序2的执行效率比源程序1高，当然所占用的存储空间也比源程序1要多。可以说是“用空间换时间”。  

图1  POJ给出的评判结果

【例2】Sum of Consecutive Prime Numbers （POJ 2739）

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.