注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

The Bloom of Youth

本博客已搬家至http://kuangqi.me

 
 
 

日志

 
 

USACO 1.5.3 Prime Palindromes超简化解法  

2009-06-15 19:18:51|  分类: 真回收站 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Prime Palindromes

    The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
 
PROGRAM NAME: pprime

INPUT FORMAT
Line 1:  Two integers, a and b
 
SAMPLE INPUT (file pprime.in)
5 500
 
OUTPUT FORMAT
The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out)
5
7
11
101
131
151
181
191
313
353
373
383
---------------------------------------------------------------------------------------------
看题,第一个思路:暴力!直接枚举所有小于10^(N-1)的数。
忘了说一下,我用的是最简单的质数算法:
bool isprm(int n)
{
    if(n==1) return false;
    for(int i=2;i<=sqrt((double)n);i++) if(n%i==0) return false;

    return true;
}
发现能过4个点。下面就超时了。
简单优化:把循环步长改成2,这样就去掉了所有的偶数。好家伙!还真管用。能过6-7个点。最后一个8死活过不去。
看题解。建议生成回文数表再判断是否是质数,觉得太复杂。仔细观察结果,发现结果的位数都是奇数。原来是这样——位数为偶数的回文数都不是质数(11除外)因为,它们都能被11整除!
为什么呢?记得能被11整除的数的特征吗?——奇数位和偶数位之差能被11整除。回文数的奇数位上的数字和偶数位上的数字之差为0,所以都可以被11整除。
这样就好了,一下就可以去掉90%的运算量。我们来看最大数据8,也就是99999999(8个9)到9999999(7个9)这九千万个数都是偶数位的,没有一个是质数回文数!
换句话说,数据7跟数据8的结果是一样的!好了~如果输入8,那就按7来处理。终于AC了~~
我承认这样有点太应试了。不过别忘了Kiss原则哦~简单的算法可以节省大量的调试时间。
另外,对题目进行数论角度的分析,是很有效的方法!
  评论这张
 
阅读(608)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018