数无限质数的方法 [英] Of Ways to Count the Limitless Primes
问题描述
Alright, so maybe I shouldn't have shrunk this question sooo much... I have seen the post on the most efficient way to find the first 10000 primes. I'm looking for all possible ways. The goal is to have a one stop shop for primality tests. Any and all tests people know for finding prime numbers are welcome.
等等:
- 查找素数的所有不同方式是什么?
推荐答案
Some prime tests only work with certain numbers, for instance, the Lucas–Lehmer test only works for Mersenne numbers.
大多数用于大数的素数测试只能告诉您某个数字可能是素数"(或者,如果该数字未通过测试,则肯定是不是).通常,您可以继续执行算法,直到极有可能是质数为止.
Most prime tests used for big numbers can only tell you that a certain number is "probably prime" (or, if the number fails the test, it is definitely not prime). Usually you can continue the algorithm until you have a very high probability of a number being prime.
查看此页面,尤其是其另请参见"部分.
Have a look at this page and especially its "See Also" section.
我认为 Miller-Rabin测试是最好的测试之一.在标准格式中,它给出了可能的质数-尽管已经显示出,如果将测试应用于3.4 * 10 ^ 14以下的数字,并且可以通过每个参数2、3、5、7、11、13的测试和17,它是绝对素数.
The Miller-Rabin test is, I think, one of the best tests. In its standard form it gives you probable primes - though it has been shown that if you apply the test to a number beneath 3.4*10^14, and it passes the test for each parameter 2, 3, 5, 7, 11, 13 and 17, it is definitely prime.
AKS测试是第一个确定性,证明的,通用的多项式时间测试.但是,据我所知,除非输入非常大,否则它的最佳实现比其他测试要慢.
The AKS test was the first deterministic, proven, general, polynomial-time test. However, to the best of my knowledge, its best implementation turns out to be slower than other tests unless the input is ridiculously large.
这篇关于数无限质数的方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!