HNU 13074 Goldbach’s Conjecture 解题报告

题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得。

比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得。

输入输出样例:

Sample Input
3
4
26
100
Sample Output
4 has 1 representation(s)
2+2
26 has 3 representation(s)
3+23
7+19
13+13
100 has 6 representation(s)
3+97
11+89
17+83
29+71
41+59
47+53

解题思路

1、计算1--32中哪些数是素数,并用bool数组进行标记。

2、对于偶数4做特殊处理,这是为了后面能统一处理其他大于4的情况。

3、假设输入的数为x,则从3开始依次遍历小于x/2的奇数,若当前数i是素数并且,x-i也是素数,符合条件。

代码如下:

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX_NUM 32
bool prim[MAX_NUM];

bool IsPrime(int n)            //this n is odd
{
    int i, hel;
    hel = sqrt(n);
    for(i=3; i<=hel; i++)
        if(n%i == 0)
            return false;
    if(i > hel)
        return true;
}
void init()
{
    int i;
    memset(prim, false, sizeof(prim));
    prim[1]=prim[2] = true;        //1, 2 is prime
    for(i=3; i<MAX_NUM; i+=2)
    {
        if(IsPrime(i) == true)
            prim[i] = true;
        //else prime[i] = false;
    }
}
int main()
{
    int n, x, i, tmp;
    int num, arr[12];
    init();
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        num=0;
        if(4 == x)
        {
            printf("4 has 1 representation(s)\n2+2\n");
        }
        else{    
            tmp = x/2;
            for(i=3; i<=tmp; i+=2)
            {
                if(prim[i] == true && prim[x-i] == true)
                {
                    arr[num++]=i;
                }

            }
            printf("%d has %d representation(s)\n",x, num);
            for(i=0; i<num; i++)
                printf("%d+%d\n",arr[i], x-arr[i]);
        }
        
    }
    return 0;
}





Database error: [Table 'ac_search_cache' is marked as crashed and should be repaired]

SELECT * FROM ac_search_cache WHERE hash = '59e7bb93a41c77849a870f5b83063f63cbb31834' LIMIT 1;