文档章节

HDU2098-分拆素数和

 木宛城主
发布于 2015/03/02 19:37
字数 1523
阅读 4
收藏 0
点赞 0
评论 0

分拆素数和

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10263    Accepted Submission(s): 4434


Problem Description
把一个偶数拆成两个不同素数的和,有几种拆法呢?
 

 

Input
输入包含一些正的偶数,其值不会超过10000,个数不会超过500,若遇0,则结束。
 

 

Output
对应每个偶数,输出其拆成不同素数的个数,每个结果占一行。
 

 

Sample Input
30 26 0
 

 

Sample Output
3 2
 

方法一

// e.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <stdio.h>
#include <math.h>
int main()
{
int n,a[10000],i,T,l,j,count;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
count=l=0;
for(i=2;i<=n-2;i++)
{
T=1;
for(j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
T=0;
break;
}
}
if(T==1)
{
a[l++]=i;

}
}
for(i=0;i<l;i++)
{

for(j=i+1;j<l;j++)
{
if(a[i]+a[j]==n)
count++;
}

}
printf("%d\n",count);
}
return 0;
}

问题分析(摘引):

求质数的文章: [原创]求质数(C语言描述) 【问题描述】:

试编写一个程序,找出2->N之间的所有质数。希望用尽可能快的方法实现。

【问题分析】:

这个问题可以有两种解法:一种是用“筛子法”,另一种是从2->N检查,找出质数。
先来简单介绍一下“筛法”,求2~20的质数,它的做法是先把2~20这些数一字排开:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
先取出数组中最小的数,是2,则判断2是质数,把后面2的倍数全部删掉。
2 | 3 5 7 9 11 13 15 17 19
接下来的最小数是3,取出,再删掉3的倍数
2 3 | 5 7 11 13 17 19
一直这样下去,直到结束。
筛法求质数的问题时,非质数的数据有很多是重复的。例如,如果有一个数3×7×17×23,那么在删除3的倍数时会删到它,删7、17、23时同样也会删到它。有一种“线性筛法”,可以安排删除的次序,使得每一个非质数都只被删除一次。从而提高效率。因为“筛法”不是我要介绍的重点,所以就不介绍了。
现在我来介绍第二种方法。用这种方法,最先想到的就是让从2~N逐一检查。如果是就显示出来,如果不是,就检查下一个。这是正确的做法,但效率却不高。当然,2是质数,那么2的倍数就不是质数,如果令i从2到N,就很冤枉地测试了4、6、8……这些数?所以第一点改建就是只测试2与所有的奇数就足够了。同理,3是质数,但6、9、12……这些3的倍数却不是,因此,如果能够把2与3的倍数跳过去而不测试,任意连续的6个数中,就只会测试2个而已。以6n,6n+1,6n+2,6n+3,6n+4,6n+5为例,6n,6n+2,6n+4是偶数,又6n+3是3的倍数,所以如果2与3的倍数都不理会,只要测试的数就只留下6n+1和6n+5而已了,因而工作量只是前面想法的2/6=1/3,应该用这个方法编程。
还有个问题,就是如果判断一个数i是否为素数。按素数的定义,也就是只有1与本身可以整除,所以可以用2~i-1去除i,如果都除不尽,i就是素数。观点对,但却与上一点一样的笨拙。当i>2时,有哪一个数可以被i-1除尽的?没有,为什么?如果i不是质数,那么i=a×b,此地a与b既不是i又不是1;正因为a>1,a至少为2,因此b最多也是i/2而已,去除i的数用不着是2~i-1,而用2~i/2就可以了。不但如此,因为i=a×b,a与b不能大于sqrt(i),为什么呢?如果a>sqrt(i),b>sqrt(i),于是a×b>sqrt(i)*sqrt(i)=i,因此就都不能整除i了。如果i不是质数,它的因子最大就是sqrt(i);换言之,用2~sqrt(i)去检验就行了。
但是,用2~sqrt(i)去检验也是浪费。就像前面一样,2除不尽,2的倍数也除不尽;同理,3除不尽,3的倍数也除不尽……最理想的方法就是用质数去除i。
但问题是这些素数从何而来?这比较简单,可以准备一个数组prime[],用来存放找到的素数,一开始它里面有2、3、5。检查的时候,就用prime[]中小于sqrt(i)的数去除i即可,如果都除不尽,i就是素数,把它放如prime[]中,因此prime[]中的素数会越来越多,直到满足个数为止!
不妨用这段说明来编写这个程序,但是程序设计的时候会有两个小问题:
1.如果只检查6n+1和6n+5?不难发现,它们的距离是4、2、4、2……所以,可以先定义一个变量gab=4,然后gab=6-gab;
2.比较是不能用sqrt(i),因为它不精确。举个例子,i=121,在数学上,sqrt(i)自然是11,但计算机里的结果可能是10.9999999,于是去除的数就是2、3、5、7,而不含11,因此121就变成质数了。解决这个问题的方法很简单,不要用开方,用平方即可。例如,如果p*p<=i,则就用p去除i。而且它的效率比开方高。

【程序清单】:

 

#include <stdio.h>

int creat_prime(int prime[],int n,int total)
{
register int i;
register int j;
register int gab=2;
register int count;
for(i=7;i<=n;i+=gab)
{
count=1;
gab=6-gab;
for(j=0;prime[j]*prime[j]<=i;j++)
{
if(i%prime[j]==0)
{
count=0;
break;
}
}
if(count)
{
prime[total]=i;
total++;
}
}

return total;
}

int main(void)
{
int prime[30000]={2,3,5};
int total=3; //找到素数的个数
int i;
int n=200000; //要查找的范围(>=6)

total=creat_prime(prime,n,total);
for(i=0;i<total;i++)
{
printf("%d ",prime[i]);
if(i && !(i%10))
putchar('\n');
}
putchar('\n');
}



 

 

 

© 著作权归作者所有

共有 人打赏支持
粉丝 2
博文 222
码字总数 199010
作品 0
黄浦
叠式的常规性转行分拆规则

限于版面的横向尺寸,对超长的叠式可以分拆转行。一般包括常规性的转行分拆、积分式的转行分拆、分子或分母的转行分拆和根式的转行分拆等几种方法。叠式转行分拆也有一定的规则,不能乱拆,否...

学术研究软件 ⋅ 2016/05/03 ⋅ 0

WPS业务下月分拆 成金山软件第三家独立子公司

5月24日消息,金山办公业务分拆工作已经接近尾声,下月将正式公布分拆消息。知情人士透露,分拆后的金山办公管理层并无变化,未来金山办公将更加关注办公软件的互联网化及移动互联网市场。 ...

红薯 ⋅ 2011/05/24 ⋅ 9

高等数学Mathematica实验题——孪生素数的输出(Output of Twin Prime Numbers)

n = 10000;f = {}; For[i = 1, Prime[i] < n, i++,If[Prime[i + 1] == Prime[i] + 2,f = Append[f, {Prime[i], Prime[i + 1]}]]];f...

hpdlzu80100 ⋅ 05/04 ⋅ 0

【转载】Python脚本判断一个数是否为素数的几种方法

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合...

摩云飞 ⋅ 2013/02/05 ⋅ 0

改进的筛素数法

最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内的素数并保存到primes[]数组中。 //by Mor...

长平狐 ⋅ 2012/12/10 ⋅ 0

改进的筛素数法

最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内的素数并保存到primes[]数组中。 //by Mor...

彭博 ⋅ 2012/04/12 ⋅ 1

筛素数法小结

筛选素数方法小结:   最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉,依次进行下去即可。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内...

老朱教授 ⋅ 2017/10/01 ⋅ 0

Python进阶系列连载(13)——Python内置高阶函数filter(下)

前言 进阶部分连载继续~ 如果还没看过我的入门连载部分,先看: https://ask.hellobi.com/blog/wangdawei/10288 当然,小编的免费入门课程已经有咯,看过连载的朋友可以看看视频再快速梳理一...

ID王大伟 ⋅ 04/28 ⋅ 0

Python3 欧拉计划 问题46-50

问题41—45参见:https://www.jianshu.com/p/15254f8060e7 46、哥德巴赫的另一个猜想 哥德巴赫曾猜想:每个奇合数可以写成一个素数和一个平方的两倍之和。 9 = 7 + 2×1^2 15 = 7 + 2×2^2 2...

AiFan ⋅ 01/03 ⋅ 0

Friso英文字符串中的英文句号被忽略

@狮子的魂 你好,想跟你请教个问题:friso在似乎会忽略英文字符串中的英文句号,在中文里则会独立分拆开来,逗号也会独立分拆出来,比如: You are my sun shine. hello, world you/are/my/...

黄冠能 ⋅ 2014/01/10 ⋅ 6

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 18分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

楠木楠 ⋅ 30分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 59分钟前 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部