判断素数及其算法优化

刺骨的言语ヽ痛彻心扉 2021-09-22 11:48 346阅读 0赞

首先，我们要清楚什么是素数？

**素数**：又称质数，一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的[因数][Link 1];否则称为[合数][Link 2]。

根据素数的定义，我们可以写成出判断一个数是不是素数的算法。

/**
         * 判断是否是素数
         *
         * @param n 目标数
         * @return true：是素数; false:不是素数
         */
        public static boolean isPrime(int n) {
            // 1 不是素数
            if (n <= 1) {
                return false;
            }
            // 由于在找 n 的因数时，只需要除到 n 开根号，所以只需 i*i<n 即可
            for (int i = 2; i * i < n; i++) {
                // 只要能被 i 整除，则返回 0
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }

我们知道如何判断一个数是不是素数后，就容易在给定的范围里寻找素数了。

不过，上面的判断素数的算法,在大范围内筛选素数的效率不是最高的。下面介绍一种Eratosthenes（埃拉托斯特尼）算法来进行素数的筛选，它的效率要高的多。

（1）先把1删除（1既不是质数也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

.......

（n）读取队列中当前最小的状态为true的数n，然后把n的倍数删去

![70][]

/**
         * Eratosthenes算法（用于筛选素数）
         *
         * @param primes 标记素数的数组
         */
        private static void Eratosthenes(boolean[] primes) {
            // 数组的长度
            int length = primes.length;
    
            // 初始化数组，标志 true 代表是素数
            for (int i = 2; i < length; i++) {
                primes[i] = true;
            }
    
            for (int i = 2; i * i < length; i++) {
                // 筛选素数
                if (primes[i]) {
                    for (int j = 2 * i; j < length; j++) {
                        // 不是素数，则继续筛选
                        if (!primes[j]) {
                            continue;
                        }
                        // 如果数 j 能被整除，则不是素数
                        if (j % i == 0) {
                            primes[j] = false;
                        }
                    }
                }
            }
        }

下面我们使用分别上面的算法，传入一个测试用例来比较两个算法筛选素数的效率。

（1）使用Eratosthenes算法

/**
         * 使用 Eratosthenes 算法寻找num以内的素数
         *
         * @param num 目标数
         */
        public static void selectPrimesByEratosthenes(int num) {
            // 定义保存素数的数组
            boolean[] primes = new boolean[num + 1];
            //统计素数个数
            int count = 0;
            // 调用 Eratosthenes 算法，筛选素数
            Eratosthenes(primes);
            // 遍历出num内的所有素数
            for (int i = 2; i <= num; i++) {
                if (primes[i]) {
                    count++;
                    System.out.println(i);
                }
            }
        }

测试代码：

public static void main(String[] args) {
            // 寻找100000以内的素数
            int n = 100000;
            long start_time = System.currentTimeMillis();
            selectPrimesByEratosthenes(n);
            long end_time = System.currentTimeMillis();
            System.out.println("selectPrimesByEratosthenes:" + (double) (end_time - start_time) + " ms");
    
        }

（2）使用一般算法

/**
         * 使用一般算法寻找素数
         *
         * @param num
         */
        public static void selectPrimeByGenerate(int num) {
            for (int i = 2; i <= num; i++) {
                if (isPrime(i)) {
                    System.out.println(i);
                }
            }
        }

测试代码：

public static void main(String[] args) {
            // 寻找100000以内的素数
            int n = 100000;
            long start_time = System.currentTimeMillis();
            selectPrimesByGenerate(n);
            long end_time = System.currentTimeMillis();
            System.out.println("selectPrimesByGenerate:" + (double) (end_time - start_time) + " ms");
    
        }

比较时间：（这里的时间还加上了打印素数的时间）

![70 1][]

![70 2][]

所以，当在大范围内筛选素数时，Eratosthenes算法效率要高的多。

[Link 1]: https://baike.so.com/doc/5383750-5620151.html
[Link 2]: https://baike.so.com/doc/556494-589163.html
[70]: /images/20210920/ac231f9cce5f446eb7881063f15d947c.png
[70 1]: /images/20210920/904c850d04d34785b543d5647ac88887.png
[70 2]: /images/20210920/c5f431c3e8b2499c92a3d557cb4015d8.png