一、埃式筛法
代码
二、线性筛法(欧拉筛法)
主要的思想就是一个质数的倍数(倍数为1除外)肯定是合数,那么我们利用这个质数算出合数,然后划掉这个合数,下次就可以不用判断它是不是质数,节省了大量的时间。
其实合数的倍数也是合数,这点也可以利用,划去其他的合数。
代码
主要的思想就是一个质数的倍数(倍数为1除外)肯定是合数,那么我们利用这个质数算出合数,然后划掉这个合数,下次就可以不用判断它是不是质数,节省了大量的时间。
其实合数的倍数也是合数,这点也可以利用,划去其他的合数。