一、打表
有时候，我们需要对某个范围内的数据进行判断，判断它是否符合某种条件，然后在接下来的很多次数据中，我们有可能会反复使用到这些判断的结果。为了减少重复计算，我们可以事先将某个范围的数据的判断结果都计算一遍，并保存起来，以后需要再使用到的时候，直接使用就可以了，这样的方式，我们可以称之为打表。
二、案例说明
质数的和与积
Description
两个质数的和是S，它们的积最大是多少？Input
一个不大于10000的正整数S，为两个质数的和。Output
一个整数，为两个质数的最大乘积。数据保证有解。Sample Input
50
Sample Output
589
思路分析
1、思路一：直接枚举
假设两个正整数x，y，并且y=s-x。那么我们只需要逐个枚举x就可以了得出x，y，且x的范围是在[2，s-2](2是最小质数)。那么接下来就是判断x、y均要是质数，如果均是质数，那么就计算它们的乘积，否则就枚举下一个。最后找出最大的乘积。
2、思路二：打表再枚举
如果我们假设两个质数是x, y，并且要满足x+y==s，我们可以逐个枚举所有的x和y（x<=y，为了不重复，因为有乘法交换律），找出最大的乘积就可以了。如何知道哪些数是质数呢，我们就可以直接通过筛法先求出最大范围内即[1~10000]的所有质数，然后我们枚举的x，y就只需要在质数里面去找就可以了。
当然是思路一中，一样可以打表再枚举，也是先找出范围内的质数，这样就避免了重复判断的计算。总之，打表可以避免重复计算，是降低时间复杂度的一种重要手段。同时也是暴力枚举中需要掌握好的技巧。
参考代码
//用筛法得出1～10000内哪些数是质数，并把质数都存在一个数组a[]中，然后x,y就只需在a[]范围内枚举。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main(){
// 用筛法打表
bool b[10010];
int a[10000];
memset(b, true, sizeof(b));
b[1] = false;
for(int i=2; i<=100; i++){ //筛法
if(b[i]){
for(int j=i; j<=10000/i; j++)
b[i*j] = false;
}
}
int k = 0;
for(int i=2; i<=10000; i++){
if(b[i]){
a[++k] = i;
}
}
// 打表完成
int s, max, cj;
cin >> s;
max = 0;
for(int i=1; i<=k; i++){
for(int j=i; j<=k; j++){
if(a[i]+a[j] == s){
cj = a[i]*a[j];
if(cj>max)
max = cj;
}
}
}
cout << cj;
return 0;
}
打表的方式是为了减少重复计算，实际上这种思路和方法也被广泛应用在我们后面的编程中，譬如『记忆化搜索』、斐波那契数用数组递推代替函数递归、『动态规划』等。这种思想值得大家去思考和学习。
