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
HINTS (use them carefully!)
题意:
给出a和b,表示a到b这个范围(5<=a<b<=100000000),输出在这个范围内的所有回文串素数。
思路:
暴搜,剪枝。
1.回文串数字的长度可能是1,2,3,4,5,6,7,8。但是长度为偶数的时候,一定能被11整除,故长度只可能是1,3,5,7,还有长度为2时的11;
2.回文串的首尾数字必须相同,那么首尾和末尾只能是1,3,7,9,还有当只有一位数的时候的5;
3.素数筛选,小于10000时直接判断,大于10000时用10000内的素数是否能整除这个数来判断。
AC:
/* TASK:pprime LANG:C++ ID:sum-g1 */ #include<stdio.h> #include<math.h> #include<string.h> int a,b; int pri[15000],prinum[15000],ans=0; int test(int num) //10000内的素数判断 { if(num == 1) return 0; for(int i = 2;i <= num/2;i += 1) if(!(num % i)) return 0; return 1; } int test2(int num) //10000外的素数判断 { for(int i = 0;i < ans;i++) { if(prinum[i] > num/2) break; if(!(num % prinum[i])) return 0; } return 1; } void pal() { for(int i = 1;i <= 9;i += 2) //1位 if(pri[i] && i <= b && i >= a) printf("%d\n",i); if(11 <= b && 11 >= a) printf("%d\n",11); //2位 for(int i = 1 ;i <= 9;i += 2) //3位 { if(i == 5) continue; for(int j = 0;j <= 9;j++) { int k = i * pow(10,2) + j * pow(10,1) + i * pow(10,0); if(k > b || k < a) continue; if(pri[k]) printf("%d\n",k); } } for(int i = 1 ;i <= 9;i += 2) //5位 { if(i == 5) continue; for(int j = 0;j <= 9;j++) for(int p = 0;p <= 9;p++) { int k = i * pow(10,4) + j * pow(10,3) + p * pow(10,2) + j * pow(10,1) + i * pow(10,0); if(k > b || k < a) continue; if(test2(k)) printf("%d\n",k); } } for(int i = 1 ;i <= 9;i += 2) //7位 { if(i == 5) continue; for(int j = 0;j <= 9;j++) for(int p = 0;p <= 9;p++) for(int q = 0;q <= 9;q++) { int k = i * pow(10,6) + j * pow(10,5) + p * pow(10,4) + q * pow(10,3) + p * pow(10,2) + j * pow(10,1) + i * pow(10,0); if(k > b || k < a) continue; if(test2(k)) printf("%d\n",k); } } } int main() { freopen("pprime.in","r",stdin); freopen("pprime.out","w",stdout); for(int i = 1;i <= 10000;i++) if(test(i)) { pri[i]=1; prinum[ans++]=i; } scanf("%d%d",&a,&b); pal(); return 0; }
相关推荐
USACO题目Dual Palindromes (dualpal)及代码解析
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
zoj 1325 Palindromes.md
poj 3376 Finding Palindromes.md
-palindromes-源码.rar
在网络浏览器中打开palindromes.html 使用的技术 使用HTML和JavaScript创建 合法的 版权所有(c)2015 Chris Swan和Phillip Shannon 该软件已获得MIT许可。 特此免费授予获得此软件和相关文档文件(“软件”)副本...
CIS 241回文 CIS 241中的作业4(第2部分)中的第2个 到期日: 2020年10月23日 程序说明: 回文是指向前和向后以相同方式拼写的字符串。 回文症的一些例子是:“雷达”,“可能是我看到的厄尔巴岛”,以及,如果您...
9 [1.2] 双重回文数 Dual Palindromes 10 [1.3] 混合牛奶 Mixing Milk 11 [1.3] 修理牛棚 Barn Repair 12 [1.3] 牛式 Prime Cryptarithm 13 [1.3] 虫洞 wormhole 14 [1.3] 滑雪课程设计Ski Course Design
该项目是多年迭代开发和综合社区知识的产物。 它没有强加特定的开发哲学或框架,因此您可以按照自己的方式自由地构建代码。 主页: : 资料来源: : 推特: 快速开始 选择以下选项之一: ...
回文 简单的回文解析应用程序,给出了前三个最大的回文 说明:mvn install在目标/文件夹中运行具有一个参数的应用程序以扫描回文(将列出第一个)
题目有 Beautiful Meadow Big String Outspread Image Transformation palindromes Sum Up
ACM题目及答案——Common permutation,Base 9 Calculator,Calendar,Sorting by Swapping,Palindromes
palindromes that can be built */ int longestPalindrome (string & s) { int result = 0 ; bool hasOdd = false ; std::unordered_map< char , int > count; for ( char ch: s) { ++count[ch]; } for (std::...
1312 Prime Cuts 简单题 1334 Basically Speaking 简单题 1337 Pi 简单题 1342 Word Index 简单题 1349 Four Quarters 简单题 1350 The Drunk Jailer 简单题 1352 Number Base Conversion 简单题 ...
设计性试验实验指导书,栈和队列, 一、验证性实验 2 实验1:顺序栈的各种基本运算 2 实验2:链栈的各种基本运算 3 实验3:顺序队列的各种基本...实验4:镜像回文(Palindromes) 10 实验5:模拟车间流水线的工作 12
2001 计算两点间的距离 2005 第几天? 2007 平方和与立方和 2010 水仙花数 2011 多项式求和 2012 素数判定 2013 蟠桃记 2018 母牛的故事 ...2029 Palindromes_easy version 2035 人见人爱A^B 2040 亲和数
1312 Prime Cuts 简单题 1334 Basically Speaking 简单题 1337 Pi 简单题 1342 Word Index 简单题 1349 Four Quarters 简单题 1350 The Drunk Jailer 简单题 1352 Number Base Conversion 简单题 ...
Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings “pop”, “noon”, “x”, ...
标题前言hdu2023求平均成绩hdu2027统计元音hud2044一只小蜜蜂…hud2029Palindromes _easy versionhud2043密码hud2040亲和数hud2021发工资咯hud2032杨辉三角 前言 今天bigsai陪伴我刷题,我很高兴在他的帮助下过了8道...
数据结构和算法模拟面试学习指南... 输入: "Dad gave mom a Tesla as a racecar" 输出: Dad, mom, racecar, 3 Palindromes 解释哈希表如何工作。 给定2个链表,其中每个链表中的每个节点代表一个字符串中的一个字符,