sidef-scripts/Math/legendre_prime_counting_function.sf

#!/usr/bin/ruby

# The Legendre phi function is defined recursively as:
#   φ(x, 0) = x
#   φ(x, a) = φ(x, a−1) − φ(floor(x/p_a), a−1), where p_a is the a-th prime number.

# From which the prime counting function, π(n), can be defined as:
#   π(n) = 0 when n < 2
#   π(n) = φ(n, a) + a - 1, where a = π(√n), n ≥ 2

# See also:
#   https://rosettacode.org/wiki/Legendre_prime_counting_function

func legendre_phi(x, a) is cached {
    return x if (a <= 0)
    var p = a.prime
    return __FUNC__(x, a-1) if (p > x)
    __FUNC__(x, a-1) - __FUNC__(idiv(x, p), 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 .. 5) {
    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))
}