素数计数函数的可行实现 [英] Feasible implementation of a Prime Counting Function

问题描述

谁能提供任何素数计数函数实现的计算上可行的伪代码?我最初尝试编写 Hardy-Wright 算法，但它的阶乘开始生成悲惨的溢出，许多其他人似乎必然会产生类似的问题.我曾在 Google 上搜索过实用的解决方案，但充其量也找到了我从未见过在传统程序中实现的非常深奥的数学.

Can anyone provide computationally feasible pseudocode of any prime-counting function implementation? I initially attempted coding the Hardy-Wright algorithm, but its factorials began generating miserable overflow, and many others appear bound to yield similar problems. I've scoured Google for practical solutions, but, at best, have found very esoteric mathematics which I haven't ever seen implemented in conventional programs.

推荐答案

素数计数函数 pi(x) 计算不超过 x 的素数，几个世纪以来一直让数学家着迷.18 世纪初，Adrien-Marie Legendre 给出了一个使用辅助函数 phi(x,a) 的公式，该公式计算不大于 x 且没有被第一个 a 素数筛过的数；例如，对于数字 1、7、11、13、17、19、23、29、31、37、41、43、47 和 49，phi(50,3) = 14.phi 函数可以计算为 phi(x,a) = phi(x,a-1) - phi(x/P(a),a-1)，其中 phi(x,1) 是不超过 x 和 P(a) 的奇数个数是第 a 个素数(从 P(1)=2 开始计算).

The prime-counting function pi(x) computes the number of primes not exceeding x, and has fascinated mathematicians for centuries. At the beginning of the eighteenth century, Adrien-Marie Legendre gave a formula using an auxiliary function phi(x,a) that counts the numbers not greater than x that are not stricken by sieving with the first a primes; for instance, phi(50,3) = 14 for the numbers 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 49. The phi function can be computed as phi(x,a) = phi(x,a-1) - phi(x/P(a),a-1), where phi(x,1) is the number of odd integers not exceeding x and P(a) is the a-th prime number (counting from P(1)=2).

function phi(x, a)
  if (phi(x, a) is in cache)
    return phi(x, a) from cache
  if (a == 1)
    return (x + 1) // 2
  t := phi(x, a-1) - phi(x // p[a], a-1)
  insert phi(x, a) = t in cache
  return t

数组 p 存储小 a 的第 a 个素数，通过筛选计算.缓存很重要；没有它，运行时间将是指数级的.给定 phi，勒让德的素数计数公式是 pi(x) = phi(x,a) + a - 1，其中 a = pi(floor(sqrt(x))).勒让德使用他的公式计算 pi(10^6)，但他报告的是 78526 而不是正确答案 78498，即使是错误的，对于复杂的手动计算来说也是惊人的接近.

An array p stores the a-th prime for small a, calculated by sieving. The cache is important; without it, run time would be exponential. Given p Legendre's prime-counting formula is pi(x) = phi(x,a) + a - 1, where a = pi(floor(sqrt(x))). Legendre used his formula to calculate pi(10^6), but he reported 78526 instead of the correct answer of 78498, which, even though wrong, was astonishingly close for an intricate manual calculation.

在 1950 年代，Derrick H. Lehmer 提出了一种改进的素数计数算法:

In the 1950s, Derrick H. Lehmer gave an improved algorithm for counting primes:

function pi(x)
  if (x < limit) return count(primes(x))
  a := pi(root(x, 4)) # fourth root of x
  b := pi(root(x, 2)) # square root of x
  c := pi(root(x, 3)) # cube root of x
  sum := phi(x,a) + (b+a-2) * (b-a+1) / 2
  for i from a+1 to b
    w := x / p[i]
    lim := pi(sqrt(w))
    sum := sum - pi(w)
    if (i <= c)
      for j from i to lim
        sum := sum - pi(w / p[j]) + j - 1
  return sum

例如，pi(10^12) = 37607912018.即使使用这些算法及其现代变体和非常快的计算机，计算大的 pi 值仍然令人震惊；在撰写本文时，最大的已知值是 pi(10^24) = 18435599767349200867866.

For example, pi(10^12) = 37607912018. Even with these algorithms, and their modern variants, and very fast computers, it remains appallingly tedious to calculate large values of pi; at this writing, the largest known value is pi(10^24) = 18435599767349200867866.

要使用此算法计算第 n 个素数，素数定理的推论将第 n 个素数 P(n) 限定在 n log n 和 n(log n + log log n) 之间，n > 5，因此在边界处计算 pi 并使用二分法确定第 n 个素数，当边界接近时切换到筛选.

To use this algorithm to calculate the n-th prime, a corollary to the Prime Number Theorem bounds the n-th prime P(n) between n log n and n(log n + log log n) for n > 5, so compute pi at the bounds and use bisection to determine the n-th prime, switching to sieving when the bounds are close.

我在我的博客的几个条目中讨论了素数.

I discuss prime numbers in several entries at my blog.

这篇关于素数计数函数的可行实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！