作业帮pascal题回文素数 描述：因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.写一个程序来计算范围[a,b](5
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/20 12:32:05
pascal题回文素数 描述：因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.写一个程序来计算范围[a,b](5
pascal题回文素数
描述：因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.
写一个程序来计算范围[a,b](5
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.