问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

PASCAL 回文素数

发布网友 发布时间:2022-04-24 04:11

我来回答

3个回答

热心网友 时间:2022-04-24 05:41

简单枚举肯定会超时

这道题有两种思路:

(1)用筛法求出1..1e8范围内的素数,然后判断每个素数是否是回文数。
(2)生成1..1e8范围内的回文数,然后判断它是否是素数。
思路1的复杂度是O(n),思路2的复杂度是O(√n*√n)=O(n),从复杂度来看两种思路没有差别。但思路1用筛法用素数要开O(n)的数组,在n=1e8是就是90M,超出了空间*,(而且有可能超时),而思路2的空间复杂度是O(1)的,所以我们用思路2。

如何按照从小到大的顺序生成回文数呢?

设生成位数为l的回文数,若l是奇数,那么从小到大枚举(l+1) div 2位的数,然后复制翻转生成一个回文数;若l是偶数,那么从小到大枚举l div 2位的数,然后复制翻转生成一个回文数。上诉两个过程交替进行就可以从小到大生成回文数了。

很有效的优化:任意偶数长度的回文数都不 可能为质数(除了11),因为它能被11整除,而11恰好只有自身和1两个因子。除2外,所有偶数均不可能是质数。

var
a,b,i,j,k,l,t:longint;
d:array[1..10000]of longint;
begin

readln(a,b);
close(input);
d[1]:=5;d[2]:=7;d[3]:=11;
t:=3;
for i:=1 to 9 do
for j:=0 to 9 do
begin
inc(t);
d[t]:=i*101+j*10;
end;
for i:=1 to 9 do
for j:=0 to 9 do
for k:=0 to 9 do
begin
inc(t);
d[t]:=i*10001+j*1010+k*100;
end;
for i:=1 to 9 do
for j:=0 to 9 do
for k:=0 to 9 do
for l:=0 to 9 do
begin
inc(t);
d[t]:=i*1000001+j*100010+k*10100+l*1000
end;
for i:=4 to t do
for j:=2 to trunc(sqrt(d[i])) do
if d[i] mod j=0 then
begin
d[i]:=0;
break;
end;

for i:=1 to t do
if a<=d[i] then
if d[i]<=b then
writeln(d[i])
else
break;
end.

参考资料:http://www.nocow.cn/index.php/USACO/pprime

热心网友 时间:2022-04-24 06:59

穷举啊~~~~~~很简单的
for i:=m to n do begin
str(i,s);j:=1;
while j<=length(s)div 2 do
if s[j]=s[length(s)+1-j] then j:=j+1;
if j=length(s) div 2 then writeln(i);
end;
这就是程序了。
(附带讲解,选我是最佳答案哦~~~)
for i:=m to n do
是穷举m到n之间的数;
str(i,s);j:=1;
将数转化为字符串,将j赋初值;
while j<=length(s)div 2 do
if s[j]=s[length(s)+1-j] then j:=j+1;
if j=length(s) div 2 then writeln(i);
end;
如果s[j]=s[length(s)+1-j],就是说两边相等,j就+1;
然后判断j有没有=length(s)div 2,如果有,说明此数为回文,输出。
回文数求出,再进行素数判断,很简单。
求素数代码太多,自己找,我想你一能找到。

热心网友 时间:2022-04-24 08:33

var a,i,n,q,j:longint;
s:string;
begin
readln(n);
if n mod 2=0 then i:=n-1
else i:=n;
while a=0 do
begin
q:=0;
i:=i+2;
for j:=2 to trunc(sqrt(i)) do
if i mod j=0 then
begin
q:=1;
break;
end;
if q=0 then
begin
str(i,s);
for j:=1 to length(s) div 2 do
if s[j]<>s[length(s)-j+1] then q:=1;
end;
if q=0 then a:=1;
end;
writeln(i);
end.
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
南师足贴的功效和用法是什么 五指运湿膏能减肥吗 清颜六白膏真的管用吗 一个手机号建了两个微信号第一个微信号密码忘了怎么找回 ug最好用的版本是什么 带“沙鸥”的诗句大全(87句) 归计狎沙鸥的意思是什么 指期乘禁马,无暇狎沙鸥。 “无机终日狎沙鸥”的出处是哪里 “无暇狎沙鸥”的出处是哪里 快餐店中餐加盟哪家好 苏小朵预煮中餐,鲜制火锅加盟可行吗? 2019报考国家公*,报名费多少钱?低保户可以减免费用吗? 求求哪位大佬给这个加密vbs的文件写个解密吧!(加密代码如下) 后门病毒专杀工具 如何利用批处理对文件进行位异或加解密? 询问VHDL语言XOR门的问题 有什么工具可以伪装编程语言? 自转的月球运动规律 牛币普拉斯社区怎么联系? 做合约代理会被骗吗? 为什么NOIP的普及组试题和提高组试题的题目都差不多啊,后面那些阅读程序写结果、 是不是都差不多啊? 合约代理是骗局吗? 我的OPPO Reno ace 手机买回来的时候上面是不是就自带一层膜呢?这层摸是不是坏了可以换? 易次元收藏的攻略在哪里 布卡漫画怎么看别人的收藏 北海买房贷款三十万二十年应该还多少钱?利率也可以?不知不说 每次打开IE浏览器时总是显示 应用程序错误 你好,华为手机串号被别人知道会不会被仿造,对手机有没有影响? NOIP的普及组和提高组的区别? 瑞士冻结61.7亿美元俄罗斯存款,俄乌冲突有何最新进展? 俄乌冲突进一步升级,该如何看待乌克兰的经济现状? 2022俄乌冲突买卢布之后会涨吗 俄乌冲突推高国际麦价,国内小麦还有上涨空间吗? 俄乌冲突加剧下,俄罗斯卢布大幅贬值的情况下,有多少富豪因此受到了影响? 白色衬衣沾上草莓汁如何去除? 高维能量1980年属猴是什么命? 自热米饭能带上飞机吗 自热食品可以带上飞机吗 飞机可以带自热米饭吗 自热饭可以带上飞机吗 火车上可以热饭吗 自热饭可以过机场安检吗 坐飞机能带自热米饭吗 自热米饭除去水包能带上飞机吗? 自热米饭能带上飞机吗 飞机上能带饭吗 自热米饭可以带上飞机吗 速热米饭能带上飞机吗 出国飞机上可带自热米饭吗?听说自热米饭可以托运? 白色衬衣沾了草莓汁怎么办啊??急急急 电动建筑机械与手持电动工具管理要点有哪些?