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





更多相关文章
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 


    		    Goldbach\s Conjecture 的解题报告
    这道题我们有2种解法,一种解法有时候用GCC交的话会超时,而另一种诗运用了哈希查找的方法,者不得不说我们的崔哲崔老师很厉害. 题目 题目描述 In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to L ...
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
一周排行
  • 1.登陆linux,下载rzsz安装包 wget http://freeware.sgi.com/source/rzsz/rzsz-3.48.tar.gz   2.tar zxvf rzsz-3.48.tar.gz解
  • Windows Server vNext Technical Preview UI Build 9841 本文出自 "技术希望快乐点(MVP)" 博客,请务必保留此出处http://hanwa.b ...
  • 搞了不短时间的win32开发了,居然SEH结构化异常没啥了解,必须补下课 现在看来,用起来比c++的标准异常处理简单,毕竟是结构化的,不支持面向对象那一套 处理函数的返回值EXCEPTION_CONTINUE_EXE
  • 介绍之前先介绍jQuery的一个方法 jQuery.event.fix(event window.event); 此方法个浏览器的event对象转换为 jQuery.event; 如果您的事件是通过jQuery方法綁 ...
  • 1.ANSI(即MBCS):为多字节字符集,它是不定长表示世界文字的编码方式.ANSI表示英文字母时就和ASCII一样,但表示其他文字时就需要用多字节.   2.Unicode:用两个字节表示一个字符的编码方式.比如 ...
  • 你需要一些顶级域名访问方式来访问你本地的项目文件而不是目录方式访问,这时候就需要配置虚拟主机,给你的目录綁定一个域名(本地的话可以通过修改 hosts 文件随便綁定什么域名比如 www.a.com 或者 locald
  • 杭電1022Train Problem I(棧)
    Train Problem I Time Limit: 2/1 MS (Java/Othe
  • HTML5 离线缓存-manifest简介 HTML 5 应用程序缓存 使用 HTML5,通过创建 cache manifest 文件,可以轻松地创建 web 应用的离线版本. 什么是应用程序缓存(Applicati ...
  • 错误情景: 最近给nginx二级域名的时候出现proxy中的"/"的问题:导致不可访问.查看了一些资料对这个进行的解释以便以后查看. server name aa.com (一):location ...
  •     [email protected]:~$ ping www.baidu.com PING www.a.shifen.com (123.125.65.82) 56(84) b