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,然后 ...
一周排行
  • 在用jqgrid做一个表格展示时,无论数据多少,页面总显示"共1页",导致无法翻页,看不到全部数据的问题. 困扰一天半,终于解决,网上没怎么看到类似问题,大多数是显示为0页等等其他问题,所以把自己 ...
  • 作者:赵明,华清远见嵌入式学院讲师. 首先按键设备相关的数据结构的定义如下所示: /* butt_drv.h */ -- typedef struct _st_key_info_matrix /* 按键数据结构 */
  • CASE6 1. SQL脚本 [[email protected] ulcase]$ cat ulcase6.sql set termout off rem host write sys$output "Buildi ...
  • sys.path和os.path1.sys.path是python搜索模块的路径集合,是个list:os.path是os的一个模块,是操作文件和目录的模块2.sys.path和PYTHONPATH首先PYTHONPA ...
  • Navicate Data Modeler 新建的表同步不到數據庫中(備忘)
    具体的Navicate Data Modeler其实可以看官网上面展示的内容的.http:
  • hbase 學習(十五)緩存機制以及可以利用SSD作爲存儲的BucketCache
    下面介绍Hbase的缓存机制: a.HBase在读取时,会以Block为单位进行cache
  • 注意: for (int i = 1; i <= aaa.length(); i++)  其中是“ i <= ",注意等号.   原题:   2520.   QuicksumTime Limit ...
  • 


    		    vs 2008安裝失敗visual studio web 創作組建安裝失敗引起
    vs 2008安装失敗-visual studio web 创作组建安装失敗引起 环境:W
  • HDU2027 統計元音
    1 #include<cstdio> 2 #include<cstrin ...
  • 在实际的生产中,我们总是要把一些繁琐重复的事情变得简单. 下面介绍一下如何批量安装系统. 执行pxe+kickstart安装需要的设备 DHCP服务器 TFTP服务器 kickstart所生成的ks.cfg的配置文件 ...