有哪些计算上可行的伪代码可以实现素数计数函数?
我最初尝试编写Hardy-Wright算法,但它的阶乘开始产生可怜的溢出,而其他许多算法似乎也会遇到类似的问题。我在谷歌上搜寻了实用的解决方案,但最多只找到了非常晦涩的数学方法,我从未见过这些方法在传统程序中得到实现。
有哪些计算上可行的伪代码可以实现素数计数函数?
我最初尝试编写Hardy-Wright算法,但它的阶乘开始产生可怜的溢出,而其他许多算法似乎也会遇到类似的问题。我在谷歌上搜寻了实用的解决方案,但最多只找到了非常晦涩的数学方法,我从未见过这些方法在传统程序中得到实现。
素数计数函数pi(x)计算不超过x的质数数量,几个世纪以来一直吸引着数学家们。在18世纪初,阿德里安-玛丽·勒让德使用辅助函数phi(x,a)给出了一个公式,该函数计算不大于x且未被前a个质数筛去的数字数量;例如,phi(50,3) = 14表示数字1、7、11、13、17、19、23、29、31、37、41、43、47和49。可以将phi函数计算为phi(x,a) = phi(x,a-1) - phi(x/P(a),a-1),其中phi(x,1)是不超过x的奇数的数量,P(a)是第a个质数(从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的所有质数,通过筛法计算。缓存很重要,没有缓存,运行时间将呈指数级增长。根据欧拉函数phi和Legendre的计数公式,pi(x) = phi(x,a) + a - 1,其中a = pi(floor(sqrt(x)))。Legendre使用他的公式计算了pi(10^6),但他报告的结果是78526,而不是正确答案78498,即使是错误的,对于一个复杂的手动计算来说,这也是惊人地接近。
在1950年代,Derrick H. Lehmer提出了一种改进的计算质数的算法:
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
5! % 7 == (((((2*3)%7)*4)%7)*5)%7
)。 - Will Ness