primeCount: Prime Counting Function pi(x)

View source: R/NumberTheory.R

primeCountR Documentation

Prime Counting Function \pi(x)


Prime counting function for counting the prime numbers less than an integer, n, using Legendre's formula. It is based on the the algorithm developed by Kim Walisch found here: kimwalisch/primecount.


primeCount(n, nThreads = NULL)



Positive number


Specific number of threads to be used. The default is NULL.


Legendre's Formula for counting the number of primes less than n makes use of the inclusion-exclusion principle to avoid explicitly counting every prime up to n. It is given by:

\pi(x) = \pi(\sqrt x) + \Phi(x, \sqrt x) - 1

Where \Phi(x, a) is the number of positive integers less than or equal to x that are relatively prime to the first a primes (i.e. not divisible by any of the first a primes). It is given by the recurrence relation (p_a is the ath prime (e.g. p_4 = 7)):

\Phi(x, a) = \Phi(x, a - 1) + \Phi(x / p_a, a - 1)

This algorithm implements five modifications developed by Kim Walisch for calculating \Phi(x, a) efficiently.

  1. Cache results of \Phi(x, a)

  2. Calculate \Phi(x, a) using \Phi(x, a) = (x / pp) * \phi(pp) + \Phi(x mod pp, a) if a <= 6

    • pp = 2 * 3 * ... * prime[a]

    • \phi(pp) = (2 - 1) * (3 - 1) * ... * (prime[a] - 1) (i.e. Euler's totient function)

  3. Calculate \Phi(x, a) using \pi(x) lookup table

  4. Calculate all \Phi(x, a) = 1 upfront

  5. Stop recursion at 6 if \sqrt x >= 13 or \pi(\sqrt x) instead of 1


Whole number representing the number of prime numbers less than or equal to n.


The maximum value of n is 2^{53} - 1


Joseph Wood


See Also



## Get the number of primes less than a billion

## Using nThreads
system.time(primeCount(10^10, nThreads = 2))

RcppAlgos documentation built on Oct. 3, 2023, 1:07 a.m.