①质数：只包含1和本身的因数的数字，例如2，3，5，7，11等。所以使用枚举法，在2~n中能找到整除的数字，就代表不是质数。

质数

②埃氏筛法

输出1千万以内所有的质数，如果采用枚举法，各个数字都像上面一样判断是否是质数，容易超时。埃氏筛法思想：合数是某个数字的倍数。时间复杂度O(nlongn)。

思路：从2开始枚举，把2的所有倍数，都标记为合数，本身不标。然后把3的倍数标记。然后发现4已经在2的时候标记过，也就是说4的倍数，肯定也是2的倍数，这时候无需把4的倍数再标记。

埃氏筛法

③欧拉筛法

欧拉筛法的时间复杂度更低，为O(n)。欧拉筛法的核心思想是每个数只被筛一次，通过最小质因数来判断当前合数是否已经被标记过。具体实现时，需要维护一个集合，里面用来存放已知的质数。对于当前数，将其依次和集合中的质数相乘，得到的数必为合数，然后筛掉。但是当当前数可以整除当前的质数时，结束循环。这样就可以达到线性复杂度，即O(n)。

思路：质数数组{2}，从2开始枚举，把2和质数数组里的每个数组都相乘，把结果都标记为合数，所以4被标记。然后枚举到3，没被标记，把他添加进质数数组，变成{2，3}，然后3和每位相乘，标记6，9。枚举到4，标记过，就不添加进数组，但是还是需要乘每位，标记8，12。 

欧拉筛