Legendre prime counting function: Difference between revisions
→{{header|Go}}: Improved 'memoization' version.
(→{{header|Wren}}: Impoved 'memoization' version.) |
(→{{header|Go}}: Improved 'memoization' version.) |
||
Line 231:
{{libheader|Go-rcu}}
===Memoized===
This runs in about
The alternative of sieving a billion numbers and then counting them takes about 4.8 seconds using the present library function though this could be cut to 1.2 seconds using a third party library such as primegen.
Line 242:
"rcu"
)
var primes = rcu.Primes(limit)▼
var memoPhi = make(map[int]int)▼
func cantorPair(x, y int) int {
Line 252 ⟶ 248:
}
return (x*x + 3*x + 2*x*y + y + y*y) / 2
func phi(x, a int) int {▼
if a == 0 {▼
return x▼
}▼
key := cantorPair(x, a)▼
if v, ok := memoPhi[key]; ok {▼
return v▼
}▼
pa := primes[a-1]▼
memoPhi[key] = phi(x, a-1) - phi(x/pa, a-1)▼
return memoPhi[key]▼
}
Line 271 ⟶ 254:
return 0
}
▲ }
a := len(primes)
var phi func(x, a int) int // recursive closure
if a < 1 {
return x
}
if a == 1 {
return x - (x >> 1)
}
▲ pa := primes[a-1]
if x <= pa {
return 1
}
▲ key := cantorPair(x, a)
▲ if v, ok := memoPhi[key]; ok {
▲ return v
}
▲ memoPhi[key] = phi(x, a-1) - phi(x/pa, a-1)
▲ return memoPhi[key]
▲ }
return phi(n, a) + a - 1
}
| |||