筛法

素数表的获取

从1~n进行枚举，判断每个数是否是素数，如果是素数则加入素数表，这种方法的枚举部分的复杂度是O（n），而判断素数的复杂度是O（√n），因此总复杂度是O（n√n）。这个复杂度对n不超过10^5的大小是没有问题的，考试时大部分涉及素数表的题目都不会超过这个范围。

这里讲一下“埃氏筛法”：

相比于简单易懂的埃氏筛法，欧拉筛法在理解上面会有些难度，但是它对于同一个数，它并不会将其重复筛去。因此，它的复杂度几乎可以说是真正做到了O（n）的程度。

其中temp = i * primes[ j ] 的思想是：

拿2，3，4，5，6，7，8，9，10，11，12，13，14，15举例

因为5是素数，则5×2=10，5×3=15，5×4=20，5×5=25，（上限为15，所以10，15筛去）

因为6是合数，则6×2=12，6×3=18，6×4=24，6×5=30，（上限为15，所以12筛去）（这里不用6×6）