![]() |
1
68
另一种方法是:
和
编辑
注意
不幸的是,我找不到声称
所以我做了几个测试。我创造了一个
对于确定性5和10,
这是我的试验台:
我跑来跑去:
在我的机器上产生质数需要30秒。对所有人的真正考验
|
![]() |
2
43
这是最优雅的方式:
Java 1.4 +。不需要进口。 那么短。如此美丽。 |
![]() |
3
12
看看 AKS primality test (以及各种优化)。它是一个在多项式时间内运行的确定性素性测试。 Java中有一个算法的实现。 from the University of Tuebingen (Germany) here |
![]() |
4
10
你迈出了消除2的所有倍数的第一步。 但是,你为什么停在那里?你可以消除除3以外的所有3的倍数,除5以外的所有5的倍数,等等。 当你按照这个推理得出结论时,你会得到 Sieve of Eratosthenes 。 |
![]() |
5
4
如果你只是想找出一个数是否是素数,那就足够了,但是如果你想找出从0到n的所有素数,一个更好的选择是 Sieve of Eratosthenes 但这将取决于Java对数组大小的限制等。 |
![]() |
6
4
你的算法对相当小的数字很有效。对于大数,应使用高级算法(例如基于椭圆曲线)。另一个想法是使用一些“pseuso素数”测试。这将很快证明一个数字是一个素数,但它们并不是100%准确。但是,它们可以帮助你比你的算法更快地排除一些数字。 最后,尽管编译器可能会为您优化此功能,但您应该编写:
|
![]() |
7
3
你所写的是最普通的程序员所做的,而且大部分时间应该足够了。 然而,如果你追求的是“最佳科学算法”,那么有许多不同的变化(具有不同的确定性水平)被记录在案 http://en.wikipedia.org/wiki/Prime_number . 例如,如果您有一个70位数字,jvm的物理限制可能会阻止您的代码运行,在这种情况下,您可以使用“筛子”等。 再说一遍,就像我说的,如果这是一个编程问题或是软件使用的一般问题,你的代码应该是完美的:) |
![]() |
8
3
根据需要测试的数字的长度,如果要求的数字在此范围内,则可以为较小的值(n<10^6)预计算质数列表,该列表将首先使用。这当然是最快的方法。 就像在其他答案中提到的 Sieve of Eratosthenes 是生成此类预计算列表的首选方法。 如果你的数字大于这个数,你可以使用拉宾的素性检验。 Rabin primality test |
![]() |
9
3
我认为这种方法是最好的。至少对我来说-
|
![]() |
10
3
由于JAISCHKE(1993)的快速测试是Miller Rabin测试的确定版本,它没有假阳性低于4759123141,因此可以应用于Java。
这不适合
这两种测试都比任何一种试验部门都要快得多。 |
![]() |
11
2
当然,素性测试有上百种,根据数量大小、特殊形式、因子大小等各有利弊。 然而,在Java中,我发现最有用的是:
它已经实现了,而且速度相当快(我发现一个1000x1000的矩阵需要大约6秒的时间来填充long02^64和确定的15),而且可能比我们人类能想到的任何东西都要优化。 它使用了 BaillieâPSW primality test ,没有已知的反例。(尽管它可能使用稍弱的测试版本,有时可能会出错。也许) |
![]() |
12
1
我在这里优化了试验部门: 它返回一个布尔值。 除isprime(n)外,还需要其他方法。
|
![]() |
13
1
算法效率:o(n^(1/2))算法 注意:下面的示例代码包含计数变量和对打印函数的调用,以便打印结果:
当输入质数2147483647时,它会产生以下输出: 进行了23170次检查,确定2147483647为质数。 |
![]() |
14
0
在Intel Atom@1.60GHz、2GB RAM、32位操作系统中测试
测试结果:
|
![]() |
Sweepy Dodo · JSON lite的格式化 6 月前 |
![]() |
giantjenga · 优化整数向量到二进制向量的转换 7 月前 |
![]() |
Zegarek · Postgresql递归查询未提供预期结果 7 月前 |
![]() |
Joe · 为什么这两个查询之间的性能存在如此大的差异? 11 月前 |
![]() |
tic-toc-choc · 在`dplyr中高效使用列表进行过滤` 11 月前 |
![]() |
Mohan · 是否有一种更快的方法来编写代码,从1:N中提取许多随机样本? 11 月前 |
![]() |
user2980746 · 在C#字典中键入xyz对的最有效方法是什么? 11 月前 |