# Legendre prime counting function

```ruby
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))
}
```

#### Output:

```
e             n   Legendre    builtin
-             -   --------    -------
1            10          4          4
2           100         25         25
3          1000        168        168
4         10000       1229       1229
5        100000       9592       9592
6       1000000      78498      78498
7      10000000     664579     664579
```

Alternative implementation of the Legendre phi function, by counting k-rough numbers <= n.

```ruby
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))
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://trizen.gitbook.io/sidef-lang/programming_tasks/l/legendre_prime_counting_function.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.