题目来自：https://www.luogu.org/problemnew/show/P1217
题目描述
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。
写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;
输入输出格式
输入格式：
第 1 行: 二个整数 a 和 b .
输出格式：
输出一个回文质数的列表，一行一个。
输入输出样例
输入样例#1：
5 500
输出样例#1：
5
7
11
101
131
151
181
191
313
353
373
383
思考：
其实判断条件就两个一个是素数判断，一个是回文判断。
素数判断有两种通用方式一个是打表，内存换时间，一个是遍历，时间换内存。
如果采用java语言来做的话，一个MLE，一个TLE。。。
代码如下：暴力遍历素数
import java.util.*;public class Main {public static boolean prime(int num){if (num % 2 == 0) {return false;}for(int i=3;i<=Math.sqrt(num);i+=2){if(num%i==0){return false;}}return true;}public static boolean isPlalindrome(int num){int one = num,y=0;do{y=y*10+one%10;}while((one/=10)!=0);if(y==num){return true;}else{return false;}}public static void main(String args[]) {Scanner scanner = new Scanner(System.in);int min = scanner.nextInt();int max = scanner.nextInt();if(max>10000000){for(int i=min;i<=10000000;i++){if(prime(i)&&isPlalindrome(i)){System.out.println(i);}}}else{for(int i=min;i<=max;i++){if(prime(i)&&isPlalindrome(i)){System.out.println(i);}}}return;}
}
代码如下：打表
import java.util.*;public class Main {public static int[] a = new int[100000010];public static void prime(){//质数表for(int i=2;i<a.length;i++){if(a[i]==0){for(int j=i+i;j<a.length;j+=i){a[j]=1;}}}}public static boolean isPlalindrome(int num){int one = num,y=0;do{y=y*10+one%10;}while((one/=10)!=0);if(y==num){return true;}else{return false;}}public static void main(String args[]) {prime();Scanner scanner = new Scanner(System.in);int min = scanner.nextInt();int max = scanner.nextInt();if(max>10000000){for(int i=min;i<=10000000;i++){if(a[i]==0&&isPlalindrome(i)){System.out.println(i);}}}else{for(int i=min;i<=max;i++){if(a[i]==0&&isPlalindrome(i)){System.out.println(i);}}}return;}
}
c语言版:
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
int i,j;
bool ss (int num) {if (num % 2 == 0) {return false;}for(int i=3;i<=sqrt(num);i+=2){if(num%i==0){return false;}}return true;
}
bool hws (int num) {int one = num,y=0;do{y=y*10+one%10;}while((one/=10)!=0);if(y==num){return true;}else{return false;}
}
int main () {int a,b;scanf ("%d %d",&a,&b);if (b>10000000) {for (i=a; i<=10000000; i++)if ((hws(i))&&(ss(i)))printf ("%d\n",i);//注意要打括号，不然会变成里层的if-else} else {for (i=a; i<=b; i++)if ((hws(i))&&(ss(i)))printf ("%d\n",i);}return 0;//好习惯
}
为啥一样的代码ｃ语言就能ＡＣ，ｊａｖａ只能ＴＬＥ呢？
先比较两者：(都采用的是ｓｑｒｔ暴力遍历)
c语言：
耗时/内存 993ms, 924KB
ｊａｖａ：
耗时/内存 4547ms, 17004KB，前面几组数据都ａｃ，最后三组ＴＬＥ。
你说气不气。
所以只能说同样的代码，ｃ对空间和时间的利用率远高于ｊａｖａ。