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
1
1
101
151
131
181
353
191
313
373
383
给定一个范围,输出在这个范围内(包含边界)的所有回文素数.
注意以后有回文数的情况,尽量先用DFS生成回文数表,然后在做处理,不要去枚举产生回文数.
这里打出回文数表以后先排序,然后二分查出上下界,把该范围中的所有素数输出即可。
代码:
/*
ID:yfr_1992
PROG:pprime
LANG:C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
vector<int> plist;
int temp[10],sz;
void dfs(int cur,int limit){
if(cur>((limit-1)>>1)){
int sum = 0;
for(int i=0;i<limit;i++)sum = sum*10 + temp[i];
plist.push_back(sum);
return;
}
for(int i=0;i<10;i++){
temp[cur] = i,temp[limit-1-cur] = i;
dfs(cur+1,limit);
}
}
bool isPrime(int x){
for(int i=2;i<=(int)sqrt(x)+1;i++){
if((x%i)==0)return false;
}
return true;
}
int bs_lower(int x){
int l = 0, r = sz-1 , m ;
while(l<=r){
m = (l+r)>>1;
if(plist[m]>=x)r = m-1;
else l = m+1;
}
return l;
}
int bs_upper(int x){
int l = 0, r = sz-1 , m ;
while(l<=r){
m = (l+r)>>1;
if(plist[m]>x)r = m-1;
else l = m+1;
}
return r;
}
int main(){
freopen("pprime.in","r",stdin);
freopen("pprime.out","w",stdout);
for(int i=1;i<=8;i++)dfs(0,i);
sort(plist.begin(),plist.end());
sz = 1;
for(int i=1;i<(int)plist.size();i++){
if(plist[i]!=plist[i-1])plist[sz++] = plist[i];
}
int a,b;
scanf("%d%d",&a,&b);
int s = bs_lower(a), e = bs_upper(b);
for(int i=s;i<=e;i++){
if(isPrime(plist[i]))printf("%d\n",plist[i]);
}
return 0;
}
分享到:
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
自己写的代码,真是的还字少了不行。。。。。。。。。。。。。。。。。。。。。
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide