POJ中和质数相关的三个例题（POJ 2262、POJ 2739、POJ 3006）

      质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。
      最小的质数是2。

【例1】goldbach's conjecture （poj 2262）

description

in 1742, christian goldbach, a german amateur mathematician, sent a letter to leonhard euler in which he made the following conjecture:

every even number greater than 4 can be

written as the sum of two odd prime numbers.

for example:

8 = 3 + 5. both 3 and 5 are odd prime numbers.

20 = 3 + 17 = 7 + 13.

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

today it is still unproven whether the conjecture is right. (oh wait, i have the proof of course, but it is too long to write it on the margin of this page.)

anyway, your task is now to verify goldbach's conjecture for all even numbers less than a million.

input

the input will contain one or more test cases.

each test case consists of one even integer n with 6 <= n < 1000000.

input will be terminated by a value of 0 for n.

output

for each test case, print one line of the form n = a + b, where a and b are odd primes. numbers and operators should be separated by exactly one blank like in the sample output below. if there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. if there is no such pair, print a line saying "goldbach's conjecture is wrong."

sample input

8

20

42

0

sample output

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

      （1）编程思路1。

      对每个输入的n，从小到大依次对3~n/2之间的奇数i进行穷举，若i和n-i均是质数，则找到一组解，退出穷举。

判断一个数num是否为质数的方法是：用2~ 中的每一个整数m去除num，若某一个m能整除num，则num不是质数；否则，m是质数。

      （2）源程序1。

#include <iostream>

#include <cmath>

using namespace std;

bool isprime(int num)

{

    int m;

    if(num==2) return true;

    for(m=2;m<=(int)sqrt((double)num);m++)

        if (num%m==0)

         return false;

    return true;

}

int main()

{

    int n,i;

    while(cin>>n&&n)

       {

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

          {

          if(isprime(i) && isprime(n-i))

                {

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

             break;

                }

          }

       }

    return 0;

}

      （3）编程思路2。

      上面的程序在穷举时，对每个穷举的整数i，都要调用函数isprime(i) 和isprime(n-i)来判断i和n-i是否为质数。实际上，可以预先生成一个判定数组flag[1000000]，并且为了节省存储空间，可将flag数组定义为char类型（每个元素只占一个字节）。元素flag[i]==’1’表示整数i是质数；flag[i]==’0’表示整数i不是质数。

      初始化数组flag的所有元素都为’1’，然后采用eratosthenes筛法进行处理。

       eratosthenes筛法的基本思想是：把某范围内的自然数从小到大依次排列好。宣布1不是质数，把它去掉；然后从余下的数中取出最小的数，宣布它为质数，并去掉它的倍数。在第1步之后，得到质数2，筛中只包含奇数；第2步之后，得到素数3，一直做下去，直到筛子为空时结束。

      采用这个思想，用如下循环完成对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.

your mission is to write a program that reports the number of representations for the given positive integer.

input

the input is a sequence of positive integers each in a separate line. the integers are between 2 and 10 000, inclusive. the end of the input is indicated by a zero.

output

the output should be composed of lines each corresponding to an input line except the last zero. an output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. no other characters should be inserted in the output.

sample input

2

3

17

41

20

666

12

53

0

sample output

1

1

2

3

0

0

1

2

      （1）编程思路1。

      先将10000以内的所有质数求出来保存到数组prime中，并记下质数的个数len。

      对于给定的测试数据n，用二重循环求出所有的连续质数和等于n的种数cnt。

      （2）源程序1。

#include <iostream>

#include <cmath>

using namespace std;

bool isprime(int num)

{

    int m;

    if(num==2) return true;

    for(m=2;m<=(int)sqrt((double)num);m++)

        if (num%m==0)

         return false;

    return true;

}

int main()

{

    int prime[2000],i,j,len=0,n,cnt,sum;

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

       {

        if(isprime(i))

            prime[len++]=i;

    }

    while (cin>>n && n!=0)

       {

        cnt=0;

        for(i=0;i<len;i++)

              {

            sum=0;

            for(j=i;j<len;j++)

                     {

                sum+=prime[j];

                if(sum>n)

                    break;

                else if(sum==n)

                            {

                    cnt++;

                    break;

                }

            }

        }

        cout<<cnt<<endl;

    }

    return 0;

}

      （3）编程思路2。

       采用打表的方法。先用二重循环构造好答案表。

    for(i=0;i<len;i++)          

       {

        sum=0;

        for(j=i;j<len;j++)

              {

            sum+=prime[j];

            if(sum>10000) break;

                     ans[sum]++;      //  连续和为sum的种数加1

             }

       }

      对于给定的测试数据n，直接查表ans[n]即可。

      （4）源程序2。

#include <iostream>

using namespace std;

int main()

{

    int flag[10000]={0},prime[2000],ans[10001]={0};

       int i,j,len=0,n,sum;

    for(i=2;i<10000;i++)           // 构造质数表

       {

        if (flag[i]==0)

              {

                     prime[len++]=i;

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

                            flag[j]=1;

              }

    }

    for(i=0;i<len;i++)            // 构造答案表

       {

        sum=0;

        for(j=i;j<len;j++)

              {

            sum+=prime[j];

            if(sum>10000) break;

                     ans[sum]++;

             }

       }

    while (cin>>n && n!=0)

       {

        cout<<ans[n]<<endl;

    }

    return 0;

}

 【例3】dirichlet's theorem on arithmetic progressions （poj 3006）

description

if a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, ..., contains infinitely many prime numbers. this fact is known as dirichlet's theorem on arithmetic progressions, which had been conjectured by johann carl friedrich gauss (1777 - 1855) and was proved by johann peter gustav lejeune dirichlet (1805 - 1859) in 1837.

for example, the arithmetic sequence beginning with 2 and increasing by 3, i.e.,

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, ... ,

contains infinitely many prime numbers

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ... .

your mission, should you decide to accept it, is to write a program to find the nth prime number in this arithmetic sequence for given positive integers a, d, and n.

input

the input is a sequence of datasets. a dataset is a line containing three positive integers a, d, and n separated by a space. a and d are relatively prime. you may assume a <= 9307, d <= 346, and n <= 210.

the end of the input is indicated by a line containing three zeros separated by a space. it is not a dataset.

output

the output should be composed of as many lines as the number of the input datasets. each line should contain a single integer and should never contain extra characters.

the output integer corresponding to a dataset a, d, n should be the nth prime number among those contained in the arithmetic sequence beginning with a and increasing by d.

fyi, it is known that the result is always less than 106 (one million) under this input condition.

sample input

367 186 151

179 10 203

271 37 39

103 230 1

27 104 185

253 50 85

1 1 1

9075 337 210

0 0 0

sample output

92809

6709

12037

103

93523

14503

2

899429

      （1）编程思路。

      定义数组char flag[1000000]用于质数的判定。元素flag[i]==’1’表示整数i是质数；flag[i]==’0’表示整数i不是质数。

      对于输入的测试数据a、d和n，采用循环找到第n个质数在原等差数列中位置i。

       count = 0; 

       for(i=0;count<n;i++) 

          { 

           if(flag[a+d*i]=='1') 

              count++; 

          } 

      （2）源程序。

#include <iostream> 

using namespace std; 

int main() 

{ 

    int a,d,n,i,j,count; 

    char flag[1000000];

    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';

    }

    flag[1]='0'; 

    while(cin>>a>>d>>n && a+d+n!=0) 

       { 

       count = 0; 

       for(i=0;count<n;i++) 

          { 

           if(flag[a+d*i]=='1') 

              count++; 

          } 

       cout<<a+d*(i-1)<<endl; 

       } 

    return 0; 

}