打表找素数

打表是典型的空间换时间的思想，尤其是需要用到判断素数的情形下，如果事先有一张素数表可以直接查找该数是否为素数，而不是到需要判断某一个数是否是素数时再去运行时判断，时间上会节省许多。

看了《算法笔记》如今自己写一下素数打表的算法：

    #include <iostream>
    using namespace std;
    #define maxn 100001//对0 ~ 100001的数进行打表
    bool vis[maxn];//用来记录该数是否被访问过，访问过了肯定不是素数，初始化是false
    bool isprime[maxn];//isprime[i] = true则i是素数，初始化是false
    void pt_init()
    {
        for(int i = 2;i < maxn;i++) 
        {
            if(!vis[i])//若没访问过，i肯定是素数
            {
                isprime[i] = true;//记录该素数
                //比x大i的数肯定不是素数
                int x = i;
                while(x <= maxn)
                {
                    vis[x] = true;
                    x += i;
                }
            }
        }
    }
    int main()
    {
        pt_init();//素数打表
        
        return 0;
    }

打表找素数

原文：https://www.cnblogs.com/Codroc/p/12348857.html