pascal题回文素数 描述:因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.写一个程序来计算范围[a,b](5
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/27 11:39:26
![pascal题回文素数 描述:因为151即是一个素数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文素数.写一个程序来计算范围[a,b](5](/uploads/image/z/10224050-50-0.jpg?t=pascal%E9%A2%98%E5%9B%9E%E6%96%87%E7%B4%A0%E6%95%B0+%E6%8F%8F%E8%BF%B0%EF%BC%9A%E5%9B%A0%E4%B8%BA151%E5%8D%B3%E6%98%AF%E4%B8%80%E4%B8%AA%E7%B4%A0%E6%95%B0%E5%8F%88%E6%98%AF%E4%B8%80%E4%B8%AA%E5%9B%9E%E6%96%87%E6%95%B0%28%E4%BB%8E%E5%B7%A6%E5%88%B0%E5%8F%B3%E5%92%8C%E4%BB%8E%E5%8F%B3%E5%88%B0%E5%B7%A6%E6%98%AF%E7%9C%8B%E4%B8%80%E6%A0%B7%E7%9A%84%29%2C%E6%89%80%E4%BB%A5+151+%E5%8F%B7%E6%98%AF%E5%9B%9E%E6%96%87%E7%B4%A0%E6%95%B0.%E5%86%99%E4%B8%80%E4%B8%AA%E7%A8%8B%E5%BA%8F%E6%9D%A5%E8%AE%A1%E7%AE%97%E8%8C%83%E5%9B%B4%5Ba%2Cb%5D%285)
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.