埃氏筛法
一个判断素数的高效算法
关于埃氏筛法的百度百科解释在这里埃拉托斯特尼筛法，当然我不可能给个百度百科的解释就撤，那会被打死的。
众所周知，素数指的是除了1和它本身之外没有其它约数的数
我们假定一个数num，那么如果我们想通过编程来判断它是不是素数，我们首先通过它的定义想到暴力枚举方法，即用for循环配合取模操作实现，c++代码如下
bool flag = true; // flag作为标志来标识这个数是不是素数，默认设置为true
for(int i=2;i<num/2;i++)
{
if(num % i == 0)
{
flag = false; // 如果能被整除了，那就不是素数，退出循环
break;
}
}
if(flag)
{
cout<<"数："<<num<<"是素数"<<endl;
}
当然这种方法就显得很麻烦，虽然直观易懂，但是时间复杂度达到了n^2级。
当然如果稍微改进一点的话就会知道把我上面的代码循环中的i < num/2改成i*i < num，时间可以缩短。但是仍不够明显。
快乐的分割线
下面我们开始埃氏筛法的学习
看过上图百度百科的同学应该明白，埃氏筛法是范围判断素数的方法，即，你给出一个数n，我用埃氏筛法能判断从1-n的所有素数出来。
原理
素数的倍数肯定不是素数
给定一个数n，我们开一个大小为n+1的bool型数组，即 bool nums[n+1] ，并全部初始化为false， 在这里声明一点，这个数组的 nums[0] 与 nums[1] 我们并不会使用到。
建立了这样一个数组之后，我们就可以直接开干啦，我们首先要找到最小的素数，即2，从而开始循环开炮
OK非常棒，现在我们已经能找出素数中的最小者了，任务完成一半！
接下来，我们应用我们的原理——素数的倍数肯定不是素数
这里有张表
| 值 | 是否是素数 |
|---|---|
| 2 | 是 |
| 3 | 是 |
| 4 | 不是（通过素数2的倍数判断） |
| 5 | 是 |
| 6 | 不是（通过素数2,3的倍数判断） |
| 7 | 是 |
| 8 | 不是（通过素数2的倍数判断） |
| 9 | 不是（通过素数3的倍数判断） |
加入我们要求10以内的素数，开一个nums[11]，然后定位找到最小的素数->2，以2为基点，开炮，把2的倍数全部打死，当然这个也是有范围的，2的倍数我们只要判断到小于n就可以了，即小于10。然后2的倍数打死完了，再找幸存的最小素数3，以3为基点，开炮，在3的炮火攻击下，上次侥幸存活的9被揪出来打死了。***我们会一直判断，直到我们的基点达到一个临界点——小于等于n的开根号，这样我们就把所有潜藏的合数敌人全部消灭了，不信你瞅瞅？ ***
原理如此，接下来附上这一部分的代码，看完代码之后我会有一个小小的问题遗留给大家思考
int main() // 这里只给出实现代码了，上面的头文件什么的都没写了
{
int num;
cin >> num;
bool* nums = new bool[num]; // 这里我们如果需要用变量创建数组的话必须这样创建喔！
for (int i = 0; i < num; i++)
{
nums[i] = true;
}
int sn = sqrt(num);
for (int i = 2; i <= sn; i++) /* 从最小的素数2开始开炮*/
{
if (nums[i])
{
for (int j = i * i; j < num; j+=i) // 此处需要注意，我们开炮的时候，第一颗炮弹直接打到i的平方上，这是避免了重复判断，j每次要增长i
{
nums[j] = false; // 跟我一起，开炮！！
}
}
}
for (int i = 2; i < num; i++)
{
if (nums[i])
{
cout << i << "\t"; // 打印出选出来的素数你看看，这里我喜欢用制表符，个人习惯，看着舒服
}
}
delete []nums; // 最后可别忘了释放指针内存哦，并且将指针置空，养成好习惯，不要野指针！
nums = nullptr;
return 0;
}
好了，代码部分结束，最后我还遗留一个问题，你们有没有发现，我们这里重复判断了？比如我已经判断12是偶数了，已经杀死了，但是我以3为基点开炮的时候，还是会再打它一次，炸尸，这会不会浪费我们的炮弹资源（时间）呢？该如何改进这个问题呢？思考一下？
网友评论