📄 usaco 1_5_2 prime palindromes 题解_leokan的blog.mht
字号:
<DIV class=3Ddate>2008=C4=EA01=D4=C226=C8=D5 =D0=C7=C6=DA=C1=F9 =
16:42</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.5.2 Prime Palindromes</H2>
<DIV class=3Dt_msgfont>Prime Palindromes<BR>The number 151 is a =
prime=20
palindrome because it is both a prime number and a palindrome (it =
is the=20
same number when read forward as backward). Write a program that =
finds all=20
prime palindromes in the range of two supplied numbers a and b (5 =
<=3D a=20
< b <=3D 100,000,000); both a and b are considered to be =
within the=20
range . <BR><BR>PROGRAM NAME: pprime<BR>INPUT FORMAT<BR>Line=20
1: Two integers, a and b <BR><BR>SAMPLE INPUT (file =
pprime.in)=20
<BR>5 500<BR><BR>OUTPUT FORMAT<BR>The <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t of palindromic primes in =
numerical=20
order, one per line. <BR>SAMPLE OUTPUT (file=20
=
pprime.out)<BR>5<BR>7<BR>11<BR>101<BR>131<BR>151<BR>181<BR>191<BR>313<BR>=
353<BR>373<BR>383<BR><BR>HINTS=20
(use them carefully!)<BR> HINT 1 =
=20
HINT 2 <BR><BR><BR><BR>Prime =
Palindromes<BR><BR>=BB=D8=CE=C4=D6=CA=CA=FD<BR><BR>=D2=EB by tim=20
=
green<BR><BR>=D2=F2=CE=AA151=BC=B4=CA=C7=D2=BB=B8=F6=D6=CA=CA=FD=D3=D6=CA=
=C7=D2=BB=B8=F6=BB=D8=CE=C4=CA=FD(=B4=D3=D7=F3=B5=BD=D3=D2=BA=CD=B4=D3=D3=
=D2=B5=BD=D7=F3=CA=C7=BF=B4=D2=BB=D1=F9=B5=C4)=A3=AC=CB=F9=D2=D4 151=20
=
=BA=C5=CA=C7=BB=D8=CE=C4=D6=CA=CA=FD=A1=A3<BR>=D0=B4=D2=BB=B8=F6=B3=CC=D0=
=F2=C0=B4=D5=D2=B3=F6=B7=B6=CE=A7[a,b](5 <=3D a < b <=3D=20
=
100,000,000)=BC=E4=B5=C4=CB=F9=D3=D0=BB=D8=CE=C4=D6=CA=CA=FD;<BR><BR>PROG=
RAM NAME: pprime<BR><BR>INPUT FORMAT<BR>=B5=DA=20
1 =D0=D0: =B6=FE=B8=F6=D5=FB=CA=FD a =BA=CD b .<BR><BR>SAMPLE =
INPUT (file pprime.in) <BR>5=20
500<BR><BR>OUTPUT =
FORMAT<BR>=CA=E4=B3=F6=D2=BB=B8=F6=BB=D8=CE=C4=D6=CA=CA=FD=B5=C4=C1=D0=B1=
=ED=A3=AC=D2=BB=D0=D0=D2=BB=B8=F6=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
=
pprime.out)<BR>5<BR>7<BR>11<BR>101<BR>131<BR>151<BR>181<BR>191<BR>313<BR>=
353<BR>373<BR>383</DIV>
<DIV align=3Dleft>
<HR>
<P></P>
<P><STRONG>USACO 1.5.2 Prime=20
=
Palindromes<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE<BR><BR>=D3=D6=CA=C7=D2=BB=
=CC=E2=C3=B6=BE=D9=CB=D1=CB=F7=B5=C4=CC=E2=C4=BF=A3=AC=CF=C8=C9=FA=B3=C9s=
qrt(100,000,000)=D2=B2=BE=CD=CA=C710000=D2=D4=C4=DA=B5=C4=D6=CA=CA=FD=A3=AC=
=D5=E2=D1=F9=C5=D0=B6=CF=CA=C7=B7=F1=D6=CA=CA=FD=CA=B1=D6=BB=D0=E8=D2=AA=C4=
=C3=D5=E2=D0=A9=CA=FD=C0=B4=B3=FD=BE=CD=D0=D0=C1=CB,=D0=A1=BC=F4=D2=BB=CF=
=C2,=BF=AA=CD=B7=D2=BB=B8=F6=CA=FD=CA=C7=C5=BC=CA=FD=B5=C4=B2=BB=BF=BC=C2=
=C7,=B3=FD11=D2=D4=CD=E2=BB=D8=CE=C4=D6=CA=CA=FD=B6=BC=CA=C7=C6=E6=CA=FD=CE=
=BB=B5=C4,=D2=F2=CE=AA=C6=E6=CA=FD=CE=BB=D6=AE=BA=CD=D3=EB=C5=BC=CA=FD=CE=
=BB=D6=AE=BA=CD=B5=C4=B2=EE=CE=AA11=B5=C4=B1=B6=CA=FD=B5=C4=CA=FD=C4=DC=D5=
=FB=B3=FD11,=B6=F8=C5=BC=CA=FD=CE=BB=B5=C4=BB=D8=CE=C4=CA=FD,=C2=FA=D7=E3=
=D6=AE=C7=B0=CC=F5=BC=FE(=3D0).=C8=BB=BA=F3=C3=B6=BE=D910^[(wa=20
div 2)] =B5=BD10^index[(wb div 2)+2]-1=20
=
=D6=D0=B5=C4=CA=FDx=D7=F7=CE=AA=C0=E0=CB=C6=D3=DAxyx=D5=E2=D1=F9=B5=C4=CA=
=FD=C0=B4=C5=D0=B6=CF=CA=C7=B7=F1=D6=CA=CA=FD. </STRONG></P>
<P><STRONG>{<BR>TASK:pprime<BR>LANG:PASCAL<BR>}<BR>program=20
pprime;<BR>const<BR> =
maxn=3D10000;<BR> =20
index:array[0..9] of=20
=
qword=3D(1,1,10,100,1000,10000,100000,1000000,10000000,100000000);<BR>var=
<BR> =20
isprime:array[2..maxn] of boolean;<BR> =20
prime:array[0..1500] of integer;<BR> =20
a,b,sqrtb,i:longint;<BR>procedure =
init;<BR>var<BR> =20
c:longint;<BR>begin<BR> =20
assign(input,'pprime.in');reset(input);<BR> =20
readln(a,b);<BR> if a>b=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
c:=3Da;<BR> &n=
bsp;=20
=
a:=3Db;<BR> &n=
bsp;=20
b:=3Dc;<BR> =20
end;<BR> =
sqrtb:=3Dtrunc(sqrt(b));<BR> =20
close(input);<BR>end;<BR>procedure=20
=
initprime;{=C9=FA=B3=C9<10000=B5=C4=D6=CA=CA=FD}<BR>var<BR>  =
; =20
i,j:integer;<BR>begin<BR> =20
fillchar(isprime,sizeof(isprime),true);<BR> for =
i:=3D2 to=20
100 do<BR> if isprime[i] =
=
then<BR>  =
;=20
for j:=3D2 to (maxn div i)=20
=
do<BR> &=
nbsp; =20
isprime[j*i]:=3Dfalse;<BR> =20
fillchar(prime,sizeof(prime),0);<BR> for i:=3D2 =
to maxn=20
do<BR> if isprime[i]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
inc(prime[0]);<BR> &=
nbsp; =20
=
prime[prime[0]]:=3Di;<BR> =
=20
end;<BR>end;<BR>procedure=20
=
check(x:longint);{=BC=EC=B2=E9=CA=C7=B7=F1=CB=D8=CA=FD}<BR>var<BR> &=
nbsp; =20
i:integer;<BR> =20
isprime:boolean;<BR>begin<BR> =20
isprime:=3Dtrue;<BR> for i:=3D1 to prime[0]=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if prime[i]>trunc(sqrt(x))+1 then=20
=
break;<BR> &nb=
sp;=20
if x mod prime[i]=3D0=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
isprime:=3Dfalse;<BR> &nbs=
p; =20
=
break;<BR> &nb=
sp; =20
end;<BR> =20
end;<BR> if isprime then=20
writeln(x);<BR>end;<BR>procedure =
make;<BR>var<BR> =20
i,num:longint;<BR> =20
j,wa,wb,k,len,code:integer;<BR> =20
st,stt:string;<BR>begin<BR> =20
assign(output,'pprime.out');rewrite(output);<BR> =
for=20
i:=3Da to 11 do<BR> if=20
isprime[i]and(i<b) then writeln(i);<BR> =20
=
wa:=3Dtrunc(ln(a)/ln(10))+1;{a=B5=C4=CE=BB=CA=FD}<BR> =20
=
wb:=3Dtrunc(ln(b)/ln(10))+1;{b=B5=C4=CE=BB=CA=FD}<BR> =
for i:=3Dindex[(wa=20
div 2)] to index[(wb div 2)+2]-1=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
str(i,st);<BR>  =
; =20
=
len:=3Dlength(st);<BR> &nb=
sp; =20
if not odd(ord(st[1])-48) then=20
=
continue;{=BC=F4=D6=A6=D2=BB=A3=AC=C1=ED=CD=E2=C6=E6=CA=FD=CA=FD=CE=BB=C4=
=C7=B8=F6=BC=F4=D6=A6=D6=B1=BD=D3+=C1=CB=D6=D0=BC=E4=CA=FD=BC=F4=C1=CB}<B=
R> =20
for j:=3D0 to 9=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
stt:=3Dst+chr(j+48);<BR> &=
nbsp; =20
for k:=3Dlen downto 1=20
=
do<BR> &=
nbsp; =20
=
stt:=3Dstt+st[k];<BR> &nbs=
p;  =
; =20
=
val(stt,num,code);<BR> &nb=
sp; =20
if (num>=3Da)and(num<=3Db)=20
=
then<BR>  =
; =
=20
=
check(num);<BR> &nbs=
p; =20
end;<BR> =20
end;<BR> close(output);<BR>end;</STRONG></P>
<P><STRONG>begin<BR> init;<BR> =
initprime;<BR> =
make;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6=B3=CC=D0=F2=BC=F2=B6=CC=B0=A1~~</STRON=
G></P><STRONG>
<CENTER><STRONG><FONT size=3D7>Prime =
Palindromes</FONT></STRONG><BR>Russ Cox=20
</CENTER>
<P>The main problem here is that we need some way to generate =
palindromes.=20
Since there are only about 10,000 palindromes less than =
100,000,000, we=20
can just test each one to see if it is prime and in the range.</P>
<P>To generate a palindrome, we start with the first half and =
reverse it.=20
The trick is that we can repeat the middle character or not repeat =
the=20
middle character. I call a palindrome with a repeated middle =
character=20
"even" (because it is of even length) and one without "odd". So =
from the=20
string "123", we can generate the even palindrome "123321" or the =
odd=20
palindrome "12321".</P>
<P>We can generate all palindromes by doing the following:</P>
<UL>
<LI>length 1: generate odd palindromes using 1..9=20
<LI>length 2: generate even palindromes using 1..9=20
<LI>length 3: generate odd palindromes using 10..99=20
<LI>length 4: generate even palindromes using 10..99=20
<LI>... </LI></UL>
<P>The "generate" function does exactly this, using "genoddeven" =
to first=20
generate the odd palindromes for a range and then the even =
ones.</P>
<P>The "gen" function generates an even or odd palindrome for a =
number by=20
converting it to a string, making a palindrome, and converting the =
resulting string back to a number. Then it tests to see if the =
number is=20
in the range and prime. If so, it is printed.</P>
<P>We could speed this up in a number of ways: use a faster =
primality=20
test, don't generate palindromes past "b", etc. But this is =
already plenty=20
fast, and doing such things makes the program more complex and =
might=20
introduce bugs.</P><PRE>#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
FILE *fout;
long a, b;
int
isprime(long n)
{
long i;
if(n =3D=3D 2)
return 1;
if(n%2 =3D=3D 0)
return 0;
for(i=3D3; i*i <=3D n; i+=3D2)
if(n%i =3D=3D 0)
return 0;
return 1;
}
void
gen(int i, int isodd)
{
char buf[30];
char *p, *q;
long n;
sprintf(buf, "%d", i);
p =3D buf+strlen(buf);
q =3D p - isodd;
while(q > buf)
*p++ =3D *--q;
*p =3D '\0';
n =3D atol(buf);
if(a <=3D n && n <=3D b && isprime(n))
fprintf(fout, "%ld\n", n);
}
void
genoddeven(int lo, int hi)
{
int i;
for(i=3Dlo; i<=3Dhi; i++)
gen(i, 1);
for(i=3Dlo; i<=3Dhi; i++)
gen(i, 0);
}
void
generate(void)
{
genoddeven(1, 9);
genoddeven(10, 99);
genoddeven(100, 999);
genoddeven(1000, 9999);
}
void
main(void)
{
FILE *fin;
fin =3D fopen("pprime.in", "r");
fout =3D fopen("pprime.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%ld %ld", &a, &b);
generate();
exit (0);
}</PRE>
<P><STRONG>master_zed writes:</STRONG></P>
<P>The problem can be simplified slightly by noticing that any =
even=20
palindrome is divisible by 11. Therefore, 11 is the ONLY even =
prime=20
palindrome. This eliminates the need to deal with 2 =
cases:</P><PRE>#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
FILE *fout;
long a, b;
int
isprime(long n)
{
long i;
if(n =3D=3D 2)
return 1;
if(n%2 =3D=3D 0)
return 0;
for(i=3D3; i*i <=3D n; i+=3D2)
if(n%i =3D=3D 0)
return 0;
return 1;
}
void
gen(int i)
{
char buf[30];
char *p, *q;
long n;
sprintf(buf, "%d", i);
p =3D buf+strlen(buf);
q =3D p - 1;
while(q > buf)
*p++ =3D *--q;
*p =3D '\0';
n =3D atol(buf);
if(a <=3D n && n <=3D b && isprime(n))
fprintf(fout, "%ld\n", n);
}
void
generate(void)
{
int i;
for (i =3D 1; i <=3D 9; i++)
gen(i);
if(a <=3D 11 && 11 <=3D b)
fprintf(fout, "11\n");
for (i =3D 10; i <=3D 9999; i++)
gen(i);
}
void
main(void)
{
FILE *fin;
fin =3D fopen("pprime.in", "r");
fout =3D fopen("pprime.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%ld %ld", &a, &b);
generate();
exit (0);
}</PRE>
<P><STRONG>Coach Rob writes:</STRONG></P>
<P>I guess I have a slightly different coding style than the =
previous two=20
solutions. This is the same idea but coded a bit more tightly =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -