素数

素数又称质数，质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。很明显，1不是素数。

判断素数

判断一个整数n是否是素数，只需把 n 被 2 ~ n-1 之间的每一个整数去除，如果都不能被整除，那么 n 就是一个素数。

常规筛选素数思路

由于素数是指除了1和它本身以外不再有其他因数的自然数，所以我们可以暴力得出1-n范围内的素数：

上面代码是暴力求解素数筛，时间复杂度为O(n²)，很显然，在比赛过程中是会时间超限的，那么，有什么办法可以补救吗？当然，是有的，下面会有介绍。

埃筛（埃拉托斯特尼筛法）

1. 埃拉托斯特尼筛法，简称埃拉晒又称埃筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
2. 要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
3. 举个栗子，在1-n中，2是最小的素数，那么可以把2的倍数筛掉，然后最小的素数是3，那么再把3的倍数筛掉，依次类推，可以得出埃筛。
4. 具体代码实现：

1、可知，埃筛的时间复杂度是O(nlogn)，在这种时间复杂度下，如果是一个比较大的区间的，比如说1到long long 范围内的数，估计也是炸掉，所以，在分析埃筛的时候，我们可以知道，会有一些重复的数被筛多次，从而导致算法的时间复杂度增加。
2、比如说，筛2的倍数的时候，6、12、等等已经被处理过，而到了筛3的倍数的时候，有些数又重复被筛了，所以，根据这一问题，后来又出现了时间复杂度更优的欧拉筛。

`

欧拉筛（欧式筛法）

1、欧拉筛是基于埃筛的基础上的优化，让时间复杂度更优的一种算法。
2、欧拉筛法的基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
具体代码实现：

欧拉筛的时间复杂度是O(n)，很明显会比普通筛以及埃筛的时间复杂度都要低，所以，欧拉筛在比赛过程中更适合用来筛选素数。

总结

对于埃筛欧拉筛算法，本人也是接触没多久，就想写篇博客用来记录一下本人的学习过程，搞懂也需要挺久的，很是惭愧，希望学习算法能够坚持下去，也坚持把自己学过的算法总结起来，这样学习才会有所提升。学海无涯，在此与大家共勉。