先实现高效的素数筛选法

然后再暴力的无平方数筛选法

然后再高效的平方数筛选法

bool vis[1000000 + 5];//首先实现最高效的素数筛选void creat_primer_table(int m){    for(int i = 2;i * i <= m;i++)    {        if(!vis[i])        {            for(int j = i * i;j <= m;j++)            {                vis[j] = 1;            }        }    }}

以上代码是最高效的素数筛选法，有几个要点需要说一下啊，首先是基底必须是素数，这部分是靠!vis[i]实现的，然后是从i*i开始筛选

下面是暴力的无平方数的筛选

bool vis[10000000 + 5];//先实现暴力求解的方式bool is_no(int x){    for(int i = 2;i * i <= x;i++)    {        if(x % (i * i) == 0)            return false;    }    return true;}

非常的暴力而且没有技术含量，这个函数只是用来判断是不是无平方数，在主函数中还需要有一个循环来配合

下面是高效的无平方数的筛选

bool vis[1000000 + 5];//vis[0]代表n是不是无平方数 void creat_table(int n,int m){    for(int i = 2;i * i <= m;i++)    {        int p = i * i;        int pos = n;        //其实在这个地方只能挑选素数        for(;;)        {            if(pos % p != 0)            {                pos++;            }            else                break;        }        for(;pos <= m;pos = pos + p)        {            vis[pos - n] =1;        }    }}

主要在第二层循环的第一个循环处，因为必须首先找到一个平方数的倍数，才能够开始进行筛选

其中vis[]数组的含义已经写在了代码的注释中了，在主函数中相应的输出部分，应该多加注意