57 lines
1.1 KiB
Plaintext
57 lines
1.1 KiB
Plaintext
func rough_count (n,k) {
|
|
|
|
# Count of k-rough numbers <= n.
|
|
|
|
func (n,p) is cached {
|
|
|
|
if (p > n.isqrt) {
|
|
return 1
|
|
}
|
|
|
|
if (p == 2) {
|
|
return (n >> 1)
|
|
}
|
|
|
|
if (p == 3) {
|
|
var t = idiv(n,3)
|
|
return (t - (t >> 1))
|
|
}
|
|
|
|
var u = 0
|
|
var t = idiv(n,p)
|
|
|
|
for (var q = 2; q < p; q.next_prime!) {
|
|
|
|
var v = __FUNC__(t - (t % q), q)
|
|
|
|
if (v == 1) {
|
|
u += prime_count(q, p-1)
|
|
break
|
|
}
|
|
|
|
u += v
|
|
}
|
|
|
|
t - u
|
|
}(n*k, k)
|
|
}
|
|
|
|
func legendre_phi(n, a) {
|
|
rough_count(n, 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))
|
|
}
|