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.