36 lines
666 B
Plaintext
36 lines
666 B
Plaintext
func mertens(n) is cached {
|
|
|
|
var lookup_size = (2 * n.iroot(3)**2)
|
|
var mertens_lookup = [0]
|
|
|
|
for k in (1..lookup_size) {
|
|
mertens_lookup[k] = (mertens_lookup[k-1] + k.moebius)
|
|
}
|
|
|
|
static cache = Hash()
|
|
|
|
func (n) {
|
|
|
|
if (n <= lookup_size) {
|
|
return mertens_lookup[n]
|
|
}
|
|
|
|
if (cache.has(n)) {
|
|
return cache{n}
|
|
}
|
|
|
|
var M = 1
|
|
var s = n.isqrt
|
|
|
|
for k in (2 .. floor(n/(s+1))) {
|
|
M -= __FUNC__(floor(n/k))
|
|
}
|
|
|
|
for k in (1..s) {
|
|
M -= (mertens_lookup[k] * (floor(n/k) - floor(n/(k+1))))
|
|
}
|
|
|
|
cache{n} = M
|
|
}(n)
|
|
}
|