质数的获取

上篇文章向大家介绍的判断质数是的方法，虽然可以很好的判断一个数是否为素数。但是如果遇到了这样的题，也难免会超时。

题目描述

    

    输出 2 - n 之间所有的素数。（包含 2 和 n ）

如果这种问题还采用一一判断的话，时间复杂度显然为O(N*N），如果时间限制是 1 s。当 N 大于 10000 就非常悬了，在加上一个 0 那就没有悬念直接超时了。

这个时候我们就需要更精进的算法————素数表。

它的核心思想是，任何合数可以通过素数（或合数）的乘积表示，而素数都（除了1和自身）不可以。

说白了实现过程就是遇到素数就要把它的倍数记做合数，遇到合数跳过。首先默认所有数为素数，0、1记做合数，从 2 开始遍历，直到 n 。

举个小例子，要求20以内的全部素数。
0、1记做合数，从 2 开始遍历， 2 是素数所以所有小于等于 20 的 2 的倍数（也就是除 2 以外的偶数）记做合数；3 是素数，所以 6，9，12， 15，18 都记做合数；4 是合数不管；5 是素数，所以10, 15, 20记做合数（20 在标记 2 的倍数的时候就已经记做合数了，不怕重复）；6不管；7是素数，14记做合数；8，9，10，12，14，15，16，18，20都是合数不管；11,13,17,19虽然都是素数，但是他们的倍数都大于20，故不用标记。

说了这么多还是要用代码实现