在竞赛中我们经常会遇到这样的题：

         求N以内（包括N）的素数。(N<=100000)

                                                             ↑注意到这里数字范围很大

        如果用传统思路去做，例如：

#include<iostream>
using namespace std;
bool su(int x)
{
 
     
    int j=1;
    for(int i=2;i<x/2+1;i++)
        if(x%i==0)
            j=0;
    return j;
}
int main()
{
    int n=0;
    cin>>n;
    for(int i=2;i<n;i++)
    {   
        if(i%2==0&i!=2)
            continue;
        if(su(i))
            cout<<i<<endl;
    }
     
     
    return 0;
}

   很自然的会时间超限，因为在后面会很大量的调用循环。

当然更好的办法是我们可以优化算法，具体怎么做可以在站内查找大佬们的做法。

但是很多时候时间不够我们想出更好的办法了，那么要怎么解决时间超限的问题呢?

那么就要用到我们可爱的打表法了

打表法是什么？

        打个比方，我们写代码提交上去过题目就相当于我们上考场考试，学霸学的好（算法高效），写题就快，就能在考试时间内答完题，而我们学渣学的差，九九乘法表还要掰手指，写题必然是慢很多的，那么我们怎样才能和学霸一样在规定时间内完成题目呢？作弊呗，我们打小抄，提前把答案抄下来，考试带进去看不就完了？打表法就是这样一个方法，或许有些偷奸耍滑，但是AC万岁啊。

打表法如何实现？

        实现打表法有个前提：全部答案都要是我们能够推导的，也就是说我们手抄九九乘法表要知道九乘九是九个九相加这种程度的知识，那么我们才能一个一个把结果记录下来，用于我们上考场去抄答案。

        那么再回到这个题，我们的思路就是用我们这繁琐的算法去把全部十万个数里面的素数记录下来，提前存到数组里面，要多少我们就输出多少。

只需要两步：

step 1:打表

代码和之前一样，我们把输出重定向，把所需的所有素数输出到一个文本文档中

#include<iostream>
using namespace std;
bool su(int x)
{
 
     
    int j=1;
    for(int i=2;i<x/2+1;i++)
        if(x%i==0)
            j=0;
    return j;
}
int main()
{
	freopen("sushu.txt","w",stdout); 
    int n=100000;
    for(int i=2;i<n;i++)
    {   
        if(i%2==0&i!=2)
            continue;
        if(su(i))
            cout<<i<<",";//这里用逗号分隔开，方便我们一会儿存入数组中
    }
     
     
    return 0;
}

然后我们就可以在我们程序所在的文件夹中找到sushu.txt这个文档，打开它就会看到多到恶心的数字，但这就是我们的小抄了。

step 2:实现

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int i=0;
	int a[100000]={这里直接复制文档里的全部内容};//那些数字放上来太长了也没啥意义，就不浪费地方了
                                              //其实没必要这么大数组，存的下就行。
	while(a[i]<=n)//要多大的输出多大的
	{
	cout<<a[i]<<endl;
	i++;
	}
	
	
	return 0;
}

总结

        打表法是我们遇到时间超限的题时不得已为之的方法，一般就是做题时候会用，我们还是应该主动去学习设计更为高效的算法，当然也不排除有的时候我们自己模拟出答案比电脑设计算法更快的情况。总体思路就是以空间换时间。

祝大家学习进步。

在竞赛中我们经常会遇到这样的题：

         求N以内（包括N）的素数。(N<=100000)

                                                             ↑注意到这里数字范围很大

        如果用传统思路去做，例如：

#include<iostream>
using namespace std;
bool su(int x)
{
 
     
    int j=1;
    for(int i=2;i<x/2+1;i++)
        if(x%i==0)
            j=0;
    return j;
}
int main()
{
    int n=0;
    cin>>n;
    for(int i=2;i<n;i++)
    {   
        if(i%2==0&i!=2)
            continue;
        if(su(i))
            cout<<i<<endl;
    }
     
     
    return 0;
}

   很自然的会时间超限，因为在后面会很大量的调用循环。

当然更好的办法是我们可以优化算法，具体怎么做可以在站内查找大佬们的做法。

但是很多时候时间不够我们想出更好的办法了，那么要怎么解决时间超限的问题呢?

那么就要用到我们可爱的打表法了

打表法是什么？

        打个比方，我们写代码提交上去过题目就相当于我们上考场考试，学霸学的好（算法高效），写题就快，就能在考试时间内答完题，而我们学渣学的差，九九乘法表还要掰手指，写题必然是慢很多的，那么我们怎样才能和学霸一样在规定时间内完成题目呢？作弊呗，我们打小抄，提前把答案抄下来，考试带进去看不就完了？打表法就是这样一个方法，或许有些偷奸耍滑，但是AC万岁啊。

打表法如何实现？

        实现打表法有个前提：全部答案都要是我们能够推导的，也就是说我们手抄九九乘法表要知道九乘九是九个九相加这种程度的知识，那么我们才能一个一个把结果记录下来，用于我们上考场去抄答案。

        那么再回到这个题，我们的思路就是用我们这繁琐的算法去把全部十万个数里面的素数记录下来，提前存到数组里面，要多少我们就输出多少。

只需要两步：

step 1:打表

代码和之前一样，我们把输出重定向，把所需的所有素数输出到一个文本文档中

#include<iostream>
using namespace std;
bool su(int x)
{
 
     
    int j=1;
    for(int i=2;i<x/2+1;i++)
        if(x%i==0)
            j=0;
    return j;
}
int main()
{
	freopen("sushu.txt","w",stdout); 
    int n=100000;
    for(int i=2;i<n;i++)
    {   
        if(i%2==0&i!=2)
            continue;
        if(su(i))
            cout<<i<<",";//这里用逗号分隔开，方便我们一会儿存入数组中
    }
     
     
    return 0;
}

然后我们就可以在我们程序所在的文件夹中找到sushu.txt这个文档，打开它就会看到多到恶心的数字，但这就是我们的小抄了。

step 2:实现

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int i=0;
	int a[100000]={这里直接复制文档里的全部内容};//那些数字放上来太长了也没啥意义，就不浪费地方了
                                              //其实没必要这么大数组，存的下就行。
	while(a[i]<=n)//要多大的输出多大的
	{
	cout<<a[i]<<endl;
	i++;
	}
	
	
	return 0;
}

总结

        打表法是我们遇到时间超限的题时不得已为之的方法，一般就是做题时候会用，我们还是应该主动去学习设计更为高效的算法，当然也不排除有的时候我们自己模拟出答案比电脑设计算法更快的情况。总体思路就是以空间换时间。

祝大家学习进步。