给定一个数X，估计其中在素数的有序列表数目可落入 [英] Given a number X, estimate where in an ordered list of primes that number may fall
问题描述
鉴于质数的$ P $对 - 计算有序列表，以及所提供的数X，我想估计大致其中X将属于在素数的列表中，并开始搜索在该点
Given a pre-calculated ordered list of primes, and a supplied number X, I want to estimate roughly where X would fall in the list of primes, and start searching at that point.
因此，我已计算和存储的素数的列表从1..2 ^ 32-1，在一个二进制文件。我有在运行针对该文件的程序方法，给我的第n个素数，随机素，许多素数分布情况等，但为了将函数添加到这个节目告诉我其中提供的数字是素数，我有想出一个方法来估计从哪里开始搜索的麻烦。这样做的天真O（n）的方法很快就变成不可行，即使是数字＆LT; 2 ^ 32。
So, I have calculated and stored a list of primes from 1..2^32-1, in a binary file. I've got methods in a program that runs against that file to give me the nth prime, a random prime, how many primes exist, etc. But in order to add a function to this program to tell me where a supplied number is prime, I am having trouble coming up with a way to estimate where to begin searching. Doing it the naïve O(n) method quickly becomes infeasible, even for numbers < 2^32.
我已经试过了素数定理的（X / LN X），并进行了研究在其他一些地区，但还没有完全找到了正确的分布，我怕我的数论是没有达到标准
I've tried the Prime Number Theorem's (x/ln x), and done research in some other areas, but haven't quite found the right distribution, and I'm afraid my number theory isn't up to par.
我在寻找类似的东西，例如。
I'm looking for something like, e.g.
1 2 3 4 5 6 .. 100 .. 500 .. 1000 .. 5000 .. 10000
2 3 5 7 11 13 .. 541 .. 3571 .. 7919 .. 48611 .. 104729
所以，查找（13）会给我一些附近，但与LT = 6，查询（7920）会给我一些＆LT; = 1000和查找（104729）会给一些与LT = 10000，等等。
So, lookup(13) would give me a number near, but <= 6, lookup(7920) would give me a number <= 1000, and lookup(104729) would give a number <= 10000, etc.
P.S。我意识到这是有几个原因一个愚蠢的方法：1）我可以将其存储在不同的路，O（1）查找; B）我可以融为一体preSS存储实质上; c）对于这样的小数目，我可以做一个主要的测试上给定的数字在运行时，跳过查找表完全消失，而会更快。我的不是在为这些问题的解决方案有兴趣的;我的真正想知道是否有一个行之有效的估计方法，其中，质数的排序列表中的给定数量可能下降的。因此，这更是一个数学/数论问题不是一个执行的问题。
P.S. I realize this is a stupid method for several reasons: a) I could store it in a different way and have O(1) lookups; b) I could compress the storage substantially; c) for such small numbers, I could do a prime test on the given number at runtime, skip the lookup table entirely, and it would be faster. I'm not interested in solutions for these issues; I genuinely want to know if there is a proven method of estimating where in a sorted list of primes a given number may fall. Hence, this is more a mathematical/number-theory question than an implementation question.
P.P.S。这不是功课。
P.P.S. It's not homework.
P.P.P.S。我做了一个计算器pretty的彻底搜查，但可能已经错过了一个直接的答案。
P.P.P.S. I did a pretty thorough search on StackOverflow, but may have missed a direct answer to this.
感谢你。
推荐答案
素数小于X的数量大约是x的数积分，丽（X）。反转功能*给出了多大的k个素数是一个很好的估计。
The number of primes less than x is approximately the logarithmic integral of x, li(x). Inverting the function* gives a very good estimate of how large the k-th prime is.
如果你想避免编程数积分，一个合理的近似值是
If you want to avoid programming the logarithmic integral, a reasonable approximation is
K 的LN的 N + K 的LN LN的 K 的 - 的 K 的
k ln n + k ln ln k - k
看后在表该点的值，可以更准确地用素数的密度在这一点估计正确的位置上。所以，如果你想要的百万黄金，并估计它是15502175，但发现，最近的黄金在这一点上是1001000个，你可以重新估计百万黄金旧的估计 - 1000 LN（15502175）
After looking at the value at that point in the table, you can estimate the correct position even more accurately by using the density of prime numbers at that point. So if you wanted the millionth prime and estimated it to be 15,502,175 but found that the nearest prime at that point was the 1,001,000-th, you could re-estimate the millionth prime as old estimate - 1000 ln(15502175).
*技术上，功能是不是双射，因此不反转的，但它是很容易反转你所关心的区域，例如x> = 2
* Technically, the function isn't bijective and hence not invertable, but it's easy enough to invert on the region you care about, say x >= 2.
这篇关于给定一个数X，估计其中在素数的有序列表数目可落入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
