<commit_before># The partial sieve function 

The partial sieve function phi(x, a) counts the numbers ≤ x that are not divisible by any of the
first a primes. This function is sometimes also named "Legendre's sum" after the French mathematician
[Adrien-Marie Legendre](https://en.wikipedia.org/wiki/Adrien-Marie_Legendre) who first studied it in
the 19th century [[1]](#References). The partial sieve function is at the heart of all combinatorial
prime counting algorithms. In fact Legendre's prime counting function
pi(x) = pi(√x) + phi(x, pi(√x)) - 1 can be computed using solely the partial sieve function, whereas
the other more advanced combinatorial prime counting algorithms require evaluating the partial sieve
function as well as other functions.

In the advanced combinatorial prime counting algorithms such as the Lagarias-Miller-Odlyzko algorithm
[[3]](#References) and the Deléglise-Rivat algorithm [[4]](#References) the partial sieve function is
mainly used as an auxiliary function during initialization. Therefore the overall performance of these
algorithms does not meaningfully depend upon the execution speed of the partial sieve function.

However, with the advent of multi-core CPUs, the partial sieve function has found another important
use case within the combinatorial prime counting algorithms. For software programs to scale well on
multi-core CPUs it is crucial that the individual worker threads are independent from each other, so
that the threads have exclusive access to the CPU's resources and in order to prevent that a thread has
to wait idle for data from another thread. In 2002 <NAME> [[5]](#References)
devised a modification to the hard special leaves algorithm so that the computation can be slit up into
independent chunks. This modification relies on the partial sieve function for generating a lookup
table of phi(x, i) results for i ∈ [0, a]. Hence now the partial sieve function's performance
has become critical for parallel implementations of the combinatorial prime counting algorithms.
The [Generate phi(x, i) lookup table](https://github.com/kimwalisch/primecount/blob/master/doc/Partial-Sieve-Function.md#generate-phix-i-lookup-table)
paragraph contains more information.

# Recursive formula

### phi(x, a) = phi(x, a - 1) - phi(x / prime[a], a - 1)

This is the main formula for the computation of the partial sieve function. As mentioned in the
introduction this formula was first described by Legendre in his book "Théorie des nombres"
[[1]](#References). When implemented in a computer program the above recursive
phi(x, a) formula with a = pi(√x) allows computing Legendre's prime counting function
pi(x) = pi(√x) + phi(x, pi(√x)) - 1 in O(x / log(x)) operations and using O(√x / log(x)) space.
In primecount this formula is implemented in
[phi.cpp](https://github.com/kimwalisch/primecount/blob/master/src/phi.cpp) (together with all
optimizations described in this document).

<NAME> Silva's paper [[6]](#References) contains a simple C implementation of this formula:

```C
static void phi(int x, int a, int sign)
{<commit_msg>Update Partial-Sieve-Function.md<commit_after># The partial sieve function 

The partial sieve function phi(x, a) counts the numbers ≤ x that are not divisible by any of the
first a primes. This function is sometimes also named "Legendre's sum" after the French mathematician
[Adrien-Marie Legendre](https://en.wikipedia.org/wiki/Adrien-Marie_Legendre) who first studied it in
the 19th century [[1]](#References). The partial sieve function is at the heart of all combinatorial
prime counting algorithms. In fact Legendre's prime counting function
pi(x) = pi(√x) + phi(x, pi(√x)) - 1 can be computed using solely the partial sieve function, whereas
the other more advanced combinatorial prime counting algorithms require evaluating the partial sieve
function as well as other functions.

In the advanced combinatorial prime counting algorithms such as the Lagarias-Miller-Odlyzko algorithm
[[3]](#References) and the Deléglise-Rivat algorithm [[4]](#References) the partial sieve function is
mainly used as an auxiliary function during initialization. Therefore the overall performance of these
algorithms does not meaningfully depend upon the execution speed of the partial sieve function.

However, with the advent of multi-core CPUs, the partial sieve function has found another important
use case within the combinatorial prime counting algorithms. For software programs to scale well on
multi-core CPUs it is crucial that the individual worker threads are independent from each other, so
that the threads have exclusive access to the CPU's resources and in order to prevent that a thread has
to wait idle for data from another thread. In 2002 <NAME> [[5]](#References)
devised a modification to the hard special leaves algorithm so that the computation can be slit up into
independent chunks. This modification relies on the partial sieve function for generating a lookup
table of phi(x, i) results for i ∈ [0, a]. Hence now the partial sieve function's performance
has become critical for parallel implementations of the combinatorial prime counting algorithms.
The [Generate phi(x, i) lookup table](https://github.com/kimwalisch/primecount/blob/master/doc/Partial-Sieve-Function.md#generate-phix-i-lookup-table)
paragraph contains more information.

# phi(x, a) in primecount

In primecount the partial sieve function is implemented in the file
[phi.cpp](https://github.com/kimwalisch/primecount/blob/master/src/phi.cpp) (and in
[PhiTiny.hpp](https://github.com/kimwalisch/primecount/blob/master/include/PhiTiny.hpp) &
[PhiTiny.cpp](https://github.com/kimwalisch/primecount/blob/master/src/PhiTiny.cpp)).
The partial sieve function phi(x, a) is also part of
[primecount's C/C++ API](https://github.com/kimwalisch/primecount/blob/master/doc/libprimecount.md#c-api-reference)
and is available in the [primecount command-line application](https://github.com/kimwalisch/primecount#installation)
via the ```--phi``` option, e.g. phi(1000, 10) can be computed using: ```primecount 1000 10 --phi```.

# Recursive formula

### phi(x, a) = phi(x, a - 1) - phi(x / prime[a], a - 1)

This is the main formula for the computation of the partial sieve function. As mentioned in the
introduction this formula was first described by Legendre in his book "Théorie des nombres"
[[1]](#References). When implemented in a computer program the above recursive
phi(x, a) formula with a = pi(√x) allows computing Legendre's prime counting function
pi(x) = pi(√x) + phi(x, pi(√x)) - 1 in O(x / log(x)) operations and using O(√x / log(x)) space.

<NAME> e Silva's paper [[6]](#References) contains a simple C implementation of this formula:

```C
static void phi(int x, int a, int sign)
{
{'fraction_non_alphanumeric': 0.08210059171597633, 'fraction_numerical': 0.006804733727810651, 'mean_word_length': 5.080035971223022, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '790538', 'n_tokens_mistral': 1910, 'n_tokens_neox': 1797, 'n_words': 878}