1234567891011121314151617181920212223242526272829303132333435 |
- #!/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))
- }
|