arithmoi Number Theory Library

The prime counting implementation in arithmoi is based on the Legendre algorithm, which uses the inclusion-exclusion principle to determine the count of primes up to a limit, denoted as $\Pi(\text{limit})$.

Core Mathematical Model

The algorithm relies on the $\Phi(m, n)$ function, which represents the number of values up to $m$ that are not divisible by any of the first $n$ primes.

Recursive Definition: $\Phi(m, n) = \Phi(m, n - 1) - \Phi(\lfloor m / p_n \rfloor, n - 1)$

• Terminating conditions: $\Phi(0, n) = 0$ and $\Phi(m, 0) = m$.
• Optimization: If $m \le p_n$, then $\Phi(m, n) = 1$.

Legendre Formula: $\Pi(\text{limit}) = \Phi(\text{limit}, \Pi(\sqrt{\text{limit}})) + \Pi(\sqrt{\text{limit}}) - 1$

Implementation Strategy

Instead of a deeply nested recursive approach, this implementation uses a bottom-up partial sieving method to improve efficiency:

1. Flattening Recursion: It replaces the recursive stack with arrays (roughs, phis, and pisndxs) to store intermediate results.
2. Partial Sieving Waves: It processes primes in waves, performing divisions and culling in batches to reduce the computational cost of building prime products.
3. Odds-only Optimization: The implementation only processes odd numbers to reduce memory requirements by half.

Complexity and Constraints

• Time Complexity: Approximately $O(\text{limit}^{3/4} / \log \text{limit})$ for large ranges.
• Memory Complexity: $O(\sqrt{\text{limit}})$.
• Practical Limit: Because memory usage is proportional to the square root of the limit, very large ranges (e.g., $2^{64}$) are not feasible with this specific algorithm due to RAM constraints. For example, sieving to $10^{16}$ requires approximately 800 MB of memory.