如何在Java中确定素数

川长思鸟来 2023-02-15 05:28 26阅读 0赞

在数学和安全性中，一个非常重要的问题是判断数字是否为质数。 在加密密码时，这非常有用。 在本教程中，您将学习在简单情况下如何查找数字是否为质数。

## 琐事 ##

我们了解到，如果数字唯一的除数是1及其本身，那么它们就是质数。 琐碎地，我们可以检查从1到其自身（不包括在内）的每个整数，并测试它是否均分。

例如，可能会想运行此算法：

//checks whether an int is prime or not.
    boolean isPrime(int n) {
        for(int i=2;i<n;i++) {
            if(n%i==0)
                return false;
        }
        return true;
    }

乍一看，这似乎还不错，但是我们可以使其更快-更快。 考虑一下，如果2除以某个整数n，那么（n / 2）也将n除。 这表明我们不必尝试2到n之间的所有整数。 现在我们可以修改算法：

//checks whether an int is prime or not.
    boolean isPrime(int n) {
        for(int i=2;2*i<n;i++) {
            if(n%i==0)
                return false;
        }
        return true;
    }

通过一些更有效的编码，我们注意到您实际上只需要向上求n的平方根，因为如果您列出一个数字的所有因子，则平方根将始终位于中间（如果碰巧不是整数，我们还是可以的，只是可能过于近似，但我们的代码仍然可以使用）。

最后，我们知道2是“奇数”素数-它恰好是唯一的偶数素数。 因此，我们只需要单独检查2，然后遍历奇数直到n的平方根即可。 最后，我们的代码类似于：

//checks whether an int is prime or not.
    boolean isPrime(int n) {
        //check if n is a multiple of 2
        if (n%2==0) return false;
        //if not, then just check the odds
        for(int i=3;i*i<=n;i+=2) {
            if(n%i==0)
                return false;
        }
        return true;
    }

如您所见，我们已经从检查每个整数（最多检查n个以发现一个数为质数）到检查整数的一半直至平方根（实际上是奇数）。 这是一个巨大的改进，尤其是考虑到数量很大时。

## 重复次数 ##

假设您编写了一个程序，要求您检查是否有很多素数； 不只是一次 即使我们上面的程序针对该算法进行了高度优化，也存在另一种特别适合这种情况的方式：Prime Sieve。

这是基本思想：

1.  假设每个大于或等于2的整数均为质数。
2.  从列表的开头开始，如果数字是质数，请从列表中减去该数字的每一个倍数。 他们不是素数。
3.  转到下一个数字（如果已被划掉），请跳过它-它不是素数。 如果未加倍，则必须是质数，加倍。
4.  重复

让我们看看这意味着什么。 考虑以下列表：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

2是质数...相乘是倍数。 现在，我们的列表如下所示：  
**2 3 4 5****6****7****8****9****10****11****12****13****14****15****16****17****18岁****19****20****…**

您会看到为什么2是唯一的质数。 现在用3进行处理，我们将6（已被删除），9、12（已被删除），15等删除。最终，您的列表将如下所示：  
**2 3 4 5****6****7****8****9****10****11****12****13****14****15****16****17****18岁****19****20****…**

我们的素数就是剩下的素数：（2,3,5,7,11,13,17,19,23,29，…）。 在代码中，您可能希望以数组的形式跟踪此列表。 这意味着您将要遍历n个数字来设置此“筛子”，但在重复调用该函数时会加以弥补，因为无论数字是否为质数，该函数都会返回一个瞬时值。 这就是它的样子。 当然，您可以根据自己的需要进行编辑：

import java.util.Arrays;
    //global array just to keep track of it in this example, 
    //but you can easily do this within another function.
    
    // will contain true or false values for the first 10,000 integers
    boolean[] primes=new boolean[10000]; 
    //set up the primesieve
    public void fillSieve() {
        Arrays.fill(primes,true);        // assume all integers are prime.
        primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
        for (int i=2;i<primes.length;i++) {
            //if the number is prime, 
            //then go through all its multiples and make their values false.
            if(primes[i]) {
                for (int j=2;i*j<primes.length;j++) {
                    primes[i*j]=false;
                }
            }
        }
    }
    
    public boolean isPrime(int n) {
        return primes[n]; //simple, huh?
    }

标记： [Java][] [素数][Link 1]

> 翻译自: [https://mkyong.com/java/how-to-determine-a-prime-number-in-java/][https_mkyong.com_java_how-to-determine-a-prime-number-in-java]

[Java]: https://mkyong.com/tag/java/
[Link 1]: https://mkyong.com/tag/prime-number/
[https_mkyong.com_java_how-to-determine-a-prime-number-in-java]: https://mkyong.com/java/how-to-determine-a-prime-number-in-java/