回文素数新.ppt

《回文素数新.ppt》由会员分享，可在线阅读，更多相关《回文素数新.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、回文素数 了解回文数了解回文数v从左到右和从右到左是看一样的。v 例：1，11，121，12321，13531等 了解素数了解素数v指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。v例：2，5，11等是素数 4，6，9等不是素数回文素数回文素数v从左到右和从右到左是看一样的素数。v例：1，2，5，151等题目题目v找出范围a,b(5=a b=100,000,000)间的所有回文质数;v限时：0.1s大致思路大致思路v思路一：先找计算出所有的回文数，再在找到的回文数中找素数；v思路二：先筛选出所有的素数，再在所找到的素数中找回文数。选择相对优化的思路选择相对优化的思路v

2、选择方案一：只需按照规律先计算出回文数，再在回文数中找素数，此方案须遍历的数的个数为回文数的个数（小于总共数的个数）；v选择方案二：需先要遍历找所有的数找素数，再找回文数v因此：不难看出，方案一效率更高些。进一步优化进一步优化v任意偶数长度的回文数都不可能是素数（除11以外），因为它都能被11整除，而11却是素数；v除2外，所有偶数均不是素数。例程（变量部分）：例程（变量部分）：vvarv a,b,i,j,k,l,t:longint;v T:text;v d:array1.10000of longint;例程（计算回文数部分）：v d1:=5;d2:=7;d3:=11;（说明：由于一二位的回（

3、说明：由于一二位的回 文素数只有这三个，文素数只有这三个，所以直接赋值）所以直接赋值）v t:=3;（控制数组坐标变量）例程（计算回文数部分）：vfor i:=1 to 9 do（求三位回文数）（求三位回文数）v for j:=0 to 9 dov beginv inc(t);v dt:=i*101+j*10;v end;例程（计算回文数部分）：vfor i:=1 to 9 do（求五位回文数）（求五位回文数）v for j:=0 to 9 dov for k:=0 to 9 dov beginv inc(t);v dt:=i*10001+j*1010+k*100;v end;例程（计算回文数

4、部分）：vfor i:=1 to 9 do（求七位回文数）（求七位回文数）v for j:=0 to 9 dov for k:=0 to 9 dov for l:=0 to 9 dov beginv inc(t);v dt:=i*1000001+j*100010+k*10100+l*1000v end;例程（找素数部分）：v for i:=4 to t do（从四开始原因：前面三个 已经是回文素数，分别是5，7，11）v for j:=2 to trunc(sqrt(di)dov if di mod j=0 thenv beginv di:=0;v break;v end;例程（找出合题意的回

5、文素数部分）：vfor i:=1 to t dov if(a=di)and(di=b)thenv writeln(f,di)v elsev break;例程（全1）vProgram aa;vvarv a,b,i,j,k,l,t:longint;v d:array1.10000of longint;v f:text;vbeginv assign(f,pprime.in);v reset(f);v readln(a,b);v close(f);v d1:=5;d2:=7;d3:=11;v t:=3;v for i:=1 to 9 dov for j:=0 to 9 dov beginv inc(t

6、);v dt:=i*101+j*10;v end;v for i:=1 to 9 dov for j:=0 to 9 dov for k:=0 to 9 dov beginv inc(t);v dt:=i*10001+j*1010+k*100;v end;v 例程（全2）vfor i:=1 to 9 dov for j:=0 to 9 dov for k:=0 to 9 dov for l:=0 to 9 dov beginv inc(t);v dt:=i*1000001+j*100010+k*10100+l*1000v end;v for i:=4 to t dov for j:=2 to trunc(sqrt(di)dov if di mod j=0 thenv beginv di:=0;v break;v end;v assign(f,pprime.out);v rewrite(f);v for i:=1 to t dov if(a=di)and(di=b)thenv writeln(f,di)v elsev break;v close(f);v vend.