详解埃式筛和欧拉筛 ----判断某个范围内的质数

客官°小女子只卖身不卖艺 2024-03-30 16:02 66阅读 0赞

## 0.判断一个数是否是质数 ##

判断一个数是否为质数,只需要判断从2--Math.sqrt(n)个数是否可以整除这个数

public static boolean is(int n) {
            for (int i = 2; i <= Math.sqrt(n); ++i) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }

## 1.最简单普通的筛选方法 ----一个个判断是否质数 ##

这里采用的是判断一个数是否质数的方法,从2-->n个数,一个一个进行判断是否质数的方法判断

public static boolean[] isPrime(int n) {
            boolean[] isPrime = new boolean[n + 1];
            for (int i = 2; i <= n; ++i) {
                isPrime[i] = is(i);
            }
            return isPrime;
    
        }
    
        public static boolean is(int n) {
            for (int i = 2; i <= Math.sqrt(n); ++i) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }

## 2.埃式筛 ##

将从2开始的质数的倍数倍的数全部去掉,剩下的就是质数

例如筛选2-20的质数

第一步:将所有的数都置为质数(true)

第二步:判断当前数是否为质数,如果是的话,将当前数的倍数的数置为非质数(false),

例如当为2的时候,将2的倍数:4,6,8,10,12,14,16,18,20置为非质数(false),然后以此类推

![7b39b7ee3bf14441ac1280ba035e2c2b.png][]

**返回值是boolean 数组:**

public static boolean[] isPrime(int n) {
            boolean[] isPrime = new boolean[n + 1];
            Arrays.fill(isPrime, 2,n+1,true);//将全部的数置为质数
            for (int i = 2; i <= n; ++i) {
                if (isPrime[i]) {
                    for (int j = i * 2; j <= n; j += i) {//将i的倍数的数全部置为false
                        isPrime[j] = false;
                    }
                }
            }
            return isPrime;
    
        }

**返回值是list集合**

public static List<Integer> isPrime(int n) {
            ArrayList<Integer> list = new ArrayList<>();
            boolean[] isPrime = new boolean[n + 1];
            //左闭右开
            Arrays.fill(isPrime, 2, n + 1, true);//将全部的数置为质数
            for (int i = 2; i <= n; ++i) {
                if (isPrime[i]) {
                    list.add(i);
                    for (int j = i * 2; j <= n; j += i) {//将i的倍数的数全部置为false
                        isPrime[j] = false;
                    }
                }
            }
            return list;
    
        }

## 3.线性筛(欧拉筛) ##

因为当进行埃式筛的时候,进行筛选的时候一个数可能被筛选多次,造成冗余:例如i=2的时候,6被置为非质数(false),在i=3的时候,6又置为非质数(false).即:每个合数只被划掉一次

线性筛思路:要求每一个数都被且仅被其最小的质因数筛掉(建议边看代码,边看例子)

![10ef62c827224b14861f6847def25143.png][]

例如:i=2进入循环,将i=2加入prime集合中,将4划掉,i=3进入集合,将i=3加入prime集合中,此时将6和9划掉,i=4时,因为不是质数,不加入集合,然后此时将8划掉,此时不能将3\*4=12划掉,因为12的最小质因数为2,因此应该依据判断i%integer==0,终止此次的for循环,i=5时将10,15划掉;i=6时将12划掉;i=7时将14划掉,i=8时将16划掉,i=9时将18划掉,i=10时,将20划掉

**返回值是list集合**

public static List<Integer> isPrime(int n) {
            ArrayList<Integer> prime = new ArrayList<>();
            boolean[] isPrime = new boolean[n + 1];
            //左闭右开
            Arrays.fill(isPrime, 2, n + 1, true);//将全部的数置为质数
            for (int i = 2; i <= n; ++i) {
                if (isPrime[i]) {
                    prime.add(i);
                }
                for (Integer integer : prime) {
                    if (integer * i > n)
                        break;
                    isPrime[integer * i] = false;
                    if (i % integer == 0)
                        break;
                }
    
            }
            return prime;
    
        }

**返回值是boolean 数组:**

public static boolean[] isPrime(int n) {
            ArrayList<Integer> prime = new ArrayList<>();
            boolean[] isPrime = new boolean[n + 1];
            //左闭右开
            Arrays.fill(isPrime, 2, n + 1, true);//将全部的数置为质数
            for (int i = 2; i <= n; ++i) {
                if (isPrime[i]) {
                    prime.add(i);
                }
                for (Integer integer : prime) {
                    if (integer * i > n)
                        break;
                    isPrime[integer * i] = false;
                    if (i % integer == 0)
                        break;
                }
    
            }
            return isPrime;
    
        }

[7b39b7ee3bf14441ac1280ba035e2c2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b599cabebbf8442183e68ae6f6f83b1a.png
[10ef62c827224b14861f6847def25143.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/867e2e346f1a4b7fa217700f6a34bac5.png