20 lines
534 B
Plaintext
20 lines
534 B
Plaintext
func legendre_phi(x, a) is cached {
|
|
return x if (a <= 0)
|
|
__FUNC__(x, a-1) - __FUNC__(idiv(x, a.prime), a-1)
|
|
}
|
|
|
|
func legendre_prime_count(n) is cached {
|
|
return 0 if (n < 2)
|
|
var a = __FUNC__(n.isqrt)
|
|
legendre_phi(n, a) + a - 1
|
|
}
|
|
|
|
print("e n Legendre builtin\n",
|
|
"- - -------- -------\n")
|
|
|
|
for n in (1 .. 9) {
|
|
printf("%d %12d %10d %10d\n", n, 10**n,
|
|
legendre_prime_count(10**n), prime_count(10**n))
|
|
assert_eq(legendre_prime_count(10**n), prime_count(10**n))
|
|
}
|