有关素数的定义:质数又称素数。一个大于 1 的自然数,除了 1 和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定 1 既不是质数也不是合数)。
生成素数的算法
在我们论坛中我们给出了一个有关素数生成算法。
这个是一个公司的面试题目,请参考 Prime numbers from 1 to 100 (打印 100 以内的素数) 页面中的内容。
如何判断一个数是不是素数
为什么要判断一个数是不是素数?因为质数 非常重要,随之数字越来越大,那么在计算时候的时间复杂度越来越高,因此我们需要快速判断一个数是不是质数。
这个问题你可能需要了解下 米勒-拉宾检验( Miller–Rabin primality test) 这个东西。
米勒-拉宾素性检验是一种素数判定法则,利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授 Gary Lee Miller 首先提出了基于广义黎曼猜想的确定性算法,由于广义黎曼猜想并没有被证明,其后由以色列耶路撒冷希伯来大学的 Michael O. Rabin 教授作出修改,提出了不依赖于该假设的随机化算法。
Java 原生
下面的代码是 Java 原生代码解决的方法。
Boolean isPrime = number > 1
&& IntStream.rangeClosed(2, (int) Math.sqrt(number))
.noneMatch(n -> (number % n == 0));
复制代码
上面的代码使用了 IntStream,并且使用数学的 Math 来进行计算。
上面的代码不太好读,可能你大部分时候都不会这么去写。
BigInteger 方法
我们可以使用 BigInteger 的 isProbablePrime 方法来近似判断。
这个近似判断就使用了 米勒-拉宾素性检验。
在面试的时候,使用这个方法就可以了,因为有时候一些 online 的 code 平台不会提供第三方的工具让你使用。
int number = 10;
BigInteger.valueOf(number).isProbablePrime(100);
复制代码
Apache Math3
这个方法就非常简单了,直接用就可以了。
也是所有方法中检验效果最好,速度最快的。
int number = 10;
Primes.isPrime(number)
复制代码
为什么呢?这是因为 Apache 的 Commons Math3 使用了一个数组,把一定范围内的素数都列出来了。
简单粗暴,所以效率最高。
范围就是 Java 整数不溢出的情况下进行判断的。
结论
素数可能会经常用到,尤其在随机数算法的时候。
同时又因为算法无法覆盖掉所有的素数,因此很多公司面试的时候都会喜欢用这个题目来为难你。
完整的代码如下:
@Test
public void testIsPrime() {
int number = 10;
Boolean isPrime = number > 1
&& IntStream.rangeClosed(2, (int) Math.sqrt(number))
.noneMatch(n -> (number % n == 0));
logger.debug(" {} Prime CORE Check is - [{}]", number, isPrime);
logger.debug(" {} Prime BigInteger Check is - [{}]", number, BigInteger.valueOf(number).isProbablePrime(100));
logger.debug(" {} Prime APACHE MATH3 Check is - [{}]", number, Primes.isPrime(number));
}
复制代码
上面测试代码的输出结果为:
15:37:02.403 [main] DEBUG com.ossez.toolkits.codebank.tests.algorithm.PrimeNumbersTest - 10 Prime CORE Check is - [false]
15:37:02.406 [main] DEBUG com.ossez.toolkits.codebank.tests.algorithm.PrimeNumbersTest - 10 Prime BigInteger Check is - [false]
15:37:02.411 [main] DEBUG com.ossez.toolkits.codebank.tests.algorithm.PrimeNumbersTest - 10 Prime APACHE MATH3 Check is - [false]
Process finished with exit code 0
复制代码
其实我们这样看,是不是简单粗暴就是最好的呢?
https://www.ossez.com/t/java/13749
评论