埃拉托斯特尼筛法 Sieve of Eratosthenes
如果一个数是另一个数的倍数,那这个数肯定不是质数。利用这个性质,可以建立一个质数数组,从2开始将素数的倍数都标注为不是质数。第一轮将4、6、8等表为非质数,然后遍历到3,发现3没有被标记为非质数,则将6、9、12等标记为非质数,一直到N为止,再数一遍质数数组中有多少质数。
埃拉托斯特尼筛法 Sieve of Eratosthenes
如果一个数是另一个数的倍数,那这个数肯定不是质数。利用这个性质,可以建立一个质数数组,从2开始将素数的倍数都标注为不是质数。第一轮将4、6、8等表为非质数,然后遍历到3,发现3没有被标记为非质数,则将6、9、12等标记为非质数,一直到N为止,再数一遍质数数组中有多少质数。