pascal题回文素数

来源：学生作业帮编辑：拍题作业网作业帮分类：综合作业时间：2024/05/01 10:06:24

pascal题回文素数
描述：因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.
写一个程序来计算范围[a,b](5

/>简单枚举肯定会超时
这道题有两种思路：
(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.

pascal题回文素数回文素数的个数,用pascal pascal程序:回文数求出所有的既是回文数又是素数的三位数.pascal求大神求解哪里错了? PASCAL将1,2,3,4,5,6,7,8,9组成一个三位数,必须是素数,回文数 pascal求打印回文数 pascal 孪生素数寻找素数 pascal PASCAL完全素数问题 c语言程序设计关于回文素数【函数与过程】回文素数 C语言:查找回文素数,找出大于整数m且最靠近m的回文素数,函数返回该回文素数.