xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);
Input
这里有许多组数据，每组包括两组数据a跟b。
Output
对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。
Sample Input
5 500
Sample Output
5
7
11
101
131
151
181
191
313
353
373
383 // 判断输入的数是否为素数，若是，则将它转为字符串判断它是否为回文
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char num[];
int palindrome(char str[])
{
int i, len, flag=;
len=strlen(str);
for(i=;i<len/;i++)
if(str[i]!=str[len--i])
{ flag=; break; }
return flag;
} int prime(int n)
{
int i, flag=;
for(i=; i<n; i++)
if(n%i==)
{ flag=; break; }
return flag;
} int main()
{
int a, b, i;
while(scanf("%d %d", &a, &b)!=EOF)
{
for(i=a;i<=b;i++)
if(prime(i))
{
itoa(i,num,);
if(palindrome(num))
puts(num);
}
printf("\n");
}
return ;
}
Time Limit Exceeded
// 缩短了判断素数时遍历的范围
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
char num[];
int palindrome(char str[])
{
int i, len, flag=;
len=strlen(str);
for(i=;i<len/;i++)
if(str[i]!=str[len--i])
{ flag=; break; }
return flag;
} int prime(int n)
{
int i, flag=, k;
k=(int)ceil(sqrt(n*1.0));
for(i=; i<=k; i++)
if(n%i==)
{ flag=; break; }
return flag;
} int main()
{
int a, b, i;
while(scanf("%d %d", &a, &b)!=EOF)
{
for(i=a;i<=b;i++)
if(prime(i))
{
itoa(i,num,);
if(palindrome(num))
puts(num);
}
printf("\n");
}
return ;
}
Time Limit Exceeded*2
// 判整数型回文方法见代码
// 判素数中的终止循环条件中无需调用sqrt
#include<stdio.h>
int palindrome(int x)
{
int i=x, j=, flag=;
while(i)
{ j=j*+i%; i/=; }
if(j==x) flag=;
return flag;
} int prime(int n)
{
int i, flag=, k;
if(n!=&&n%==) flag=;
else
{
for(i=; i*i<=n; i++)
if(n%i==)
{ flag=; break; }
}
return flag;
} int main()
{
int a, b, i;
while(scanf("%d %d", &a, &b)!=EOF)
{
for(i=a;i<=b;i++)
if(prime(i))
if(palindrome(i))
printf("%d\n", i);
printf("\n");
}
return ;
}
Time Limit Exceeded*3
// 偶数除2外都不是素数
// 给定范围内最大的素数回文为9989899.
// 除了11外，任意偶数长度的回文都是11的倍数
#include<stdio.h>
int palindrome(int x)
{
int i=x, j=, flag=;
while(i)
{ j=j*+i%; i/=; }
if(j==x) flag=;
return flag;
} int prime(int n)
{
int i, flag=;
for(i=; i*i<=n; i++)
if(n%i==)
{ flag=; break; }
return flag;
} int main()
{
int a, b, i;
while(scanf("%d %d", &a, &b)!=EOF)
{
for(i=a%?a:a+;i<=b&&i<=;i+=)
{
if(i>&&i< || i>=&&i< || i>=&&i<)
continue;
if(prime(i)&&palindrome(i))
printf("%d\n", i);
}
printf("\n");
}
return ;
}
Time Limit Exceeded*4
// 打表。。。一次遍历输出
#include<stdio.h>
#include<process.h> int palindrome(int x)
{
int i=x, j=, flag=;
while(i)
{ j=j*+i%; i/=; }
if(j==x) flag=;
return flag;
} int prime(int n)
{
int i, flag=;
for(i=; i*i<=n; i++)
if(n%i==)
{ flag=; break; }
return flag;
} int main()
{
FILE *fp;
if((fp=fopen("Ntest.txt","wt"))==NULL)
{
printf("Error!\n");
exit();
}
int j=;
for(int i=;i<=;i++)
if(prime(i)&&palindrome(i))
{
j++;
if(j%) fprintf(fp, "%d, ", i);
else fprintf(fp, "%d, \n", i);
}
fprintf(fp, "\n\n%d", j);
printf("Done!\n");
fclose(fp);
return ;
}
打表代码
#include<stdio.h>
#define N 779 int table[N]=
{
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , ,
}; int main()
{
int a, b, i;
while(scanf("%d %d", &a, &b)!=EOF)
{
for(i=;i<N;i++)
if(table[i]>=a&&table[i]<=b)
printf("%d\n", table[i]);
printf("\n");
}
return ;
}
AC