报告所有小于 n 的素数 [英] reporting all prime numbers less than n

问题描述

我需要打印所有小于给定数 n 的素数.我可以使用 Eratothenes 筛，但该算法的运行时间不是 O(n).这个问题有没有 O(n) 时间的解决方案?

解决方案

我不认为你会找到一种算法来检查任意数的素性，其时间复杂度为 O(n).我很确定 NSA(以及任何其他处理加密问题的组织)对此不会很满意 :-)

获得 O(n) 或更佳方法的唯一方法是预先计算(例如)前五千万个素数(或使用 其他人已经预先计算好的列表) 并将其用作查找.我在本地有一个这样的文件，只需在它上面运行 grep 以查看数字是否为素数.它对任意数字没有帮助，但我很少需要使用那么大的数字.当然，加密专家会认为这样一个列表对于他们的目的来说非常小.

而且，如果将其转换为位图(前 5000 万素数大约为 120M)，您甚至可以通过简单地将数字转换为字节偏移量和位掩码来将复杂度降低到 O(1) - 一对位移和/或按位运算.

然而，在 O(n) 的时间复杂度中，获取低于某个 n 的质数的 list 肯定是可行的.阿特金和伯恩斯坦论文详细介绍了阿特金筛网的声明:><块引用>

我们引入了一种算法，该算法使用 O(N/log(log(N))) 加法计算直到 N 的素数 ...

这实际上比 O(n) 稍微好.

但是，它仍然不太可能与查找解决方案竞争.我的建议是使用 Atkin 或 Eratosthenes 来列出一个列表——这并不重要，因为你只会做这点一次，所以性能并不重要.

然后使用列表本身来检查素性.

I need to print all the prime numbers less than a given number n. I can use sieve of Eratothenes but the running time of that algorithm IS NOT O(n). Is there any O(n) time solution for this problem?

解决方案

I don't think you'll find an algorithm for checking an arbitrary number for primality with an O(n) time complexity. I'm pretty certain the NSA (and any other organisations that deal with crypto issues) wouldn't be very happy with that :-)

The only way you'll get an O(n) or better way is to pre-calculate (for example) the first fifty million primes (or use someone else's already-precalculated list) and use that as a lookup. I have such a file locally and it's a simple matter of running grep over it to see if the number is prime. It doesn't help for arbitrary numbers but I rarely have to use ones that big. Crypto guys, of course, would consider such a list vanishingly small for their purposes.

And, if you turn it into a bitmap (about 120M for the first fifty million primes), you can even even reduce the complexity to O(1) by simply turning the number into a byte offset and bit mask - a couple of bit shifts and/or bitwise operations.

However, getting a list of the primes below a certain n is certainly doable in O(n) time complexity. The Atkin and Bernstein paper detailing the Sieve of Atkin claims:

We introduce an algorithm that computes the prime numbers up to N using O(N/log(log(N))) additions ...

which is actually slightly better than O(n).

However, it's still unlikely to compete with a lookup solution. My advice would be to use Atkin or Eratosthenes to make a list - it doesn't really matter since you'll only be doing this bit once so performance would not be critical.

Then use the list itself for checking primality.

这篇关于报告所有小于 n 的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！