algorithm - 素数计数函数和连续素数的乘积能用多项式时间计算吗？

Question

在我一直使用的两个算法中，我使用了两个函数:

1. pi(n):=质数个数 <= n, 和
2. R(n):=r，其中 prod(p_i,i=1,r)<=n 但 n < prod(p_i,i =1,r+1) 其中 p_i 是第 i 个素数。

基本上 pi(n) 是著名的素数计数函数，R(n) 只是计算连续素数的乘积，直到达到边界 n 并返回使用的质数数量，例如:

R(12)=2 因为 2*3<=12 但 2*3*5>12 又例如

R(100)=3 因为 2*3*5<=100 但 2*3*5*7>100。

我们一直在和我的教授讨论计算这些函数的运行时间。我知道随着时间的推移它近似于 x/ln(x) 的 pi(n)，但我对某些东西有疑问:

1. R(n) 可以用多项式时间计算吗？在我看来，通过使用动态规划，我们可以通过知道 2*3*5*...*p_(i-1) 来计算乘积 2*3*5*...*p_i，因此问题简化为得到下一个素数，据我所知可以用多项式时间计算(PRIMES在P中)。
2. 另外，因为我们知道我们可以在多项式时间内确定一个数是否为素数，这不应该意味着 pi(n) 可以在多项式时间内计算出来吗？ (使用动态规划也会有所帮助)。

如果有人能帮助我澄清这些问题或指出正确的方向，我将不胜感激!谢谢!

Answer 1

有一些方法可以在亚线性时间内计算 pi(n)。谷歌搜索“legendre phi”或“lehmer prime counting function”，或搜索最近的工作“lagarias miller odlyzko prime counting function”。 Lehmer 的方法不难编程；我在 my blog 讨论它.