找到前n个素数? [英] Finding first n primes?

问题描述

可能重复:
在python中列出N以下所有素数的最快方法

Possible Duplicate:
Fastest way to list all primes below N in python

尽管我已经编写了一个函数来查找n(primes(10) -> [2, 3, 5, 7])下的所有素数，但我仍在努力寻找一种查找前n个素数的快速方法.最快的方法是什么?

Although I already have written a function to find all primes under n (primes(10) -> [2, 3, 5, 7]), I am struggling to find a quick way to find the first n primes. What is the fastest way to do this?

推荐答案

从估计值g(n) = n log n + n log log n *开始，该估计值估计n> 5的第n个素数的大小.

Start with the estimate g(n) = n log n + n log log n*, which estimates the size of the nth prime for n > 5.

然后对该估计值进行筛分. g(n)给出了一个高估，这是可以的，因为我们可以简单地丢弃生成的大于所需n的多余素数.

Then run a sieve on that estimate. g(n) gives an overestimate, which is okay because we can simply discard the extra primes generated which are larger than the desired n.

然后考虑"最快列出python中N以下所有素数的方法".

如果您担心代码的实际运行时间(而不是算法时间复杂度的数量级)，请考虑使用使用numpy的解决方案之一(而不是"pure python"解决方案之一) ).

If you are concerned about the actual runtime of the code (instead of the order of magnitude of the time complexity of the algorithm), consider using one of the solutions that use numpy (instead of one of the "pure python" solutions).

*当我写log时，是指自然对数.

*When I write log I mean the natural logarithm.

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