素数计数函数和连续素数的乘积能用多项式时间计算吗？
Can the prime-counting function and product of consecutive primes be calculated in polynomial time?
在我一直使用的两个算法中，我使用了两个函数：
- pi(n):=素数个数 <= n, and
- R(n):=r，其中 prod(p_i,i=1,r)<=n 但 n < prod(p_i,i=1,r+1) 其中 p_i 是 i-第 th 个素数。
基本上pi(n)就是著名的素数计数函数，R(n)只是计算连续素数的乘积，直到达到边界 n 和 returns 使用的质数数量，例如：
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)，但我对某些东西有疑问：
- R(n)可以用多项式时间计算吗？从我的角度来看，通过使用动态规划，我们可以通过知道 2*3*5*...*p_(i-1) 来计算乘积 2*3*5*...*p_i，所以问题减少到获得下一个素数，据我所知它可以在多项式时间内计算（PRIMES 在 P 中）。
- 又因为我们知道我们可以在多项式时间内判断一个数是否为素数，那不就意味着pi(n)可以在多项式时间内计算出来吗？ （使用动态规划也会有所帮助）。
如果有人能帮助我澄清这些问题或指出正确的方向，我将不胜感激！谢谢！
对于任何 n，您都可以在 O(n^(1/2)) 时间内轻松确定它是否为素数（检查是否可被 2,3,4...,sqrt(n) 整除），因此您可以只遍历 n 并随时保留一个计数器。如果将素数存储在列表中，您甚至可以加快检查每个数字是否为素数的速度（检查是否可被 2,3,5...整除，最接近 sqrt(n) 的素数）。所以这个寻找 pi(n) 的算法应该是 O(n^(3/2)).
所以假设您 运行 该算法并将素数存储在列表中。然后对于 R(n)，您可以遍历它们以获得它们的累积乘积，并且一旦超过 n 就 return。我不确定这样做的时间复杂度是多少，但它会很小。可能类似于 O(log(n))，肯定比 O(n) 更快。把这两个放在一起，你应该得到比 O(n^(5/2)).
更快的东西
有一些方法可以在亚线性时间内计算 pi(n)。 Google "legendre phi" 或 "lehmer prime counting function"，或最近的工作 "lagarias miller odlyzko prime counting function"。 Lehmer 的方法不难编程；我在 my blog.
讨论
在我一直使用的两个算法中，我使用了两个函数：
- pi(n):=素数个数 <= n, and
- R(n):=r，其中 prod(p_i,i=1,r)<=n 但 n < prod(p_i,i=1,r+1) 其中 p_i 是 i-第 th 个素数。
基本上pi(n)就是著名的素数计数函数，R(n)只是计算连续素数的乘积，直到达到边界 n 和 returns 使用的质数数量，例如：
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)，但我对某些东西有疑问：
- R(n)可以用多项式时间计算吗？从我的角度来看，通过使用动态规划，我们可以通过知道 2*3*5*...*p_(i-1) 来计算乘积 2*3*5*...*p_i，所以问题减少到获得下一个素数，据我所知它可以在多项式时间内计算（PRIMES 在 P 中）。
- 又因为我们知道我们可以在多项式时间内判断一个数是否为素数，那不就意味着pi(n)可以在多项式时间内计算出来吗？ （使用动态规划也会有所帮助）。
如果有人能帮助我澄清这些问题或指出正确的方向，我将不胜感激！谢谢！
对于任何 n，您都可以在 O(n^(1/2)) 时间内轻松确定它是否为素数（检查是否可被 2,3,4...,sqrt(n) 整除），因此您可以只遍历 n 并随时保留一个计数器。如果将素数存储在列表中，您甚至可以加快检查每个数字是否为素数的速度（检查是否可被 2,3,5...整除，最接近 sqrt(n) 的素数）。所以这个寻找 pi(n) 的算法应该是 O(n^(3/2)).
所以假设您 运行 该算法并将素数存储在列表中。然后对于 R(n)，您可以遍历它们以获得它们的累积乘积，并且一旦超过 n 就 return。我不确定这样做的时间复杂度是多少，但它会很小。可能类似于 O(log(n))，肯定比 O(n) 更快。把这两个放在一起，你应该得到比 O(n^(5/2)).
更快的东西有一些方法可以在亚线性时间内计算 pi(n)。 Google "legendre phi" 或 "lehmer prime counting function"，或最近的工作 "lagarias miller odlyzko prime counting function"。 Lehmer 的方法不难编程；我在 my blog.
讨论