今天在做一个算法题的时候遇到一个需要求质数的情况，但是本人比较菜只会暴力做法，所以在此记录学习一下质数筛选除了暴力以外的其它做法！
注意：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数
题目
暴力做法
直接根据定义写一个检测这个数是不是质数的方法，明显超时了
代码语言：javascript复制class Solution {
public int countPrimes(int n) {
int res = 0;
for(int i = 1;i < n;i ){
res = res isPrime(i);
}
return res;
}
//验证一个数是不是素数
public int isPrime(int num){
if(num <= 1) return 0;
for(int i = 2;i < num;i ){
if(num%i == 0) return 0;
}
return 1;
}
}上面这个还可以优化一下，因为并不需要isPrime判断到num-1，其实到sqrt(num)就行了，但是还是超时，这里判断还可以使用 i * i <= num 来判断，但是在有的题里面可能会溢出 i*i，所以就可以使用i <= num/i来判断，这三种都可以使用，看个人喜好了吧
class Solution {
public int countPrimes(int n) {
int res = 0;
for(int i = 1;i < n;i ){
res = res isPrime(i);
}
return res;
}
//验证一个数是不是素数
public int isPrime(int num){
if(num <= 1) return 0;
for(int i = 2;i <= num/i;i ){
if(num%i == 0) return 0;
}
return 1;
}
}普通筛选
Java里面没有Bit数组这种类型所以我使用的是Bitset，普通筛选就是将这个数的2倍、3倍 … 全部筛掉因为这些不止除了1和本身的因子，判断一个数是不是质数就只需要判断在不在Bitset里面即可
代码语言：javascript复制import java.util.BitSet;
class Solution {
public int countPrimes(int n) {
int res = 0;
BitSet prime = new BitSet();
for(int i = 2;i <= n/i;i ){
if(!prime.get(i)){
for(int j = 2 * i;j < n && j > 0;j =i){
prime.set(j);
}
}
}
for(int i = 2;i < n;i ){
if(!prime.get(i))res ;
}
return res;
}
}埃氏筛法
埃氏筛法就是将前面j = 2 * i 变成 j = i * i 这里，其它类似
import java.util.BitSet;
class Solution {
public int countPrimes(int n) {
int res = 0;
BitSet prime = new BitSet();
for(int i = 2;i <= n/i;i ){
if(!prime.get(i)){
for(int j = i * i;j < n ;j =i){
prime.set(j);
}
}
}
for(int i = 2;i < n;i ){
if(!prime.get(i))res ;
}
return res;
}
}上面这几种筛法看似可以的 ，但是存在重复筛选的情况，比如 2 * 3 * 5这个数就会被筛很多便，所以就出现了欧拉筛选
欧拉筛选
欧拉筛的原理是什么，欧拉筛是根据这个数的最小质因（只因）数来进行筛的，每个数只会被自身最小质因数来筛选，所以这里面就有两个比较重要的了，是怎么确保只被筛选一次以及如何确保不会被漏筛
如何确保只被筛一次
if(i % prime[j] == 0) break; 这就是被确保只被筛选一次，因为这里如果不break的话，那么接下来就是i * prime[j 1] 这个数而 i % prime[j] = 0，所以i = m * prime[j]，所以t = i * prime[j 1] = m * prime[j] * prime[j 1]，欧拉筛就是通过最小质因数来筛的而这个数的最小质因数是prime[j] 所以可以退出，在i = m * prime[j 1]时候才会被筛选不然会在后面重复筛
如何确保不会漏筛 首先一个大于1的自然数可以分为质数与合数，质数不用管，因为不会被筛选出去，而一个合数都可以变为由一个最小质因子 p * 一个数 m 得到，而p一定是小于该合数的，所以当运行到i 为这个合数的时候，i这个数已经在前面被筛掉了，因为i 同时也是倍数，所以当i = m的时候，p * m就把 当前i给筛掉了
代码语言：javascript复制class Solution {
int cnt = 0;
int []isPrime = new int[5000010]; // 1 为合数 0为质数
int []prime = new int[5000010];
public int countPrimes(int n) {
for(int i = 2;i < n;i ){
if(isPrime[i] == 0){
prime[ cnt] = i;
}
for(int j = 1;j <= cnt && prime[j] * i < n;j ){
isPrime[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
}
