# primecount - Man Page

count prime numbers

## Synopsis

**primecount** *x* [*options*]

## Description

Count the number of primes less than or equal to x (<= 10^31) using fast implementations of the combinatorial prime counting function algorithms. By default primecount counts primes using Xavier Gourdon’s algorithm which has a runtime complexity of O(x^(2/3) / log^2 x) operations and uses O(x^(2/3) * log^3 x) memory. primecount is multi-threaded, it uses all available CPU cores by default.

## Options

- -d, --deleglise-rivat
Count primes using the Deleglise-Rivat algorithm.

- -g, --gourdon
Count primes using Xavier Gourdon’s algorithm (default algorithm).

- -l, --legendre
Count primes using Legendre’s formula.

- --lehmer
Count primes using Lehmer’s formula.

- --lmo
Count primes using the Lagarias-Miller-Odlyzko algorithm.

- -m, --meissel
Count primes using Meissel’s formula.

- --Li
Approximate pi(x) using the Eulerian logarithmic integral: Li(x), with Li(x) = li(x) - li(2).

- --Li-inverse
Approximate the nth prime using the inverse Eulerian logarithmic integral: Li^-1(x).

- -n, --nth-prime
Calculate the nth prime.

- -p, --primesieve
Count primes using the sieve of Eratosthenes.

- --phi
*X A* phi(x, a) counts the numbers <= x that are not divisible by any of the first a primes.

- -R, --RiemannR
Approximate pi(x) using the Riemann R function: R(x).

- --RiemannR-inverse
Approximate the nth prime using the inverse Riemann R function: R^-1(x).

- -s, --status[=
*NUM*] Show the computation progress e.g. 1%, 2%, 3%, ... Show

*NUM*digits after the decimal point:**--status=1**prints 99.9%.- --test
Run various correctness tests and exit.

- --time
Print the time elapsed in seconds.

- -t, --threads=
*NUM* Set the number of threads, 1 <=

*NUM*<= CPU cores. By default primecount uses all available CPU cores.- -v, --version
Print version and license information.

- -h, --help
Print this help menu.

## Advanced Options for the Deleglise-Rivat Algorithm

- --P2
Compute the 2nd partial sieve function.

- --S1
Compute the ordinary leaves.

- --S2-trivial
Compute the trivial special leaves.

- --S2-easy
Compute the easy special leaves.

- --S2-hard
Compute the hard special leaves.

### Tuning factor

The alpha tuning factor mainly balances the computation of the S2_easy and S2_hard formulas. By increasing alpha the runtime of the S2_hard formula will usually decrease but the runtime of the S2_easy formula will increase. For large pi(x) computations with x >= 10^25 you can usually achieve a significant speedup by increasing alpha.

The alpha tuning factor is also very useful for verifying pi(x) computations. You compute pi(x) twice but for the second computation you use a slightly different alpha factor. If the results of both pi(x) computations match then pi(x) has been verified successfully.

- -a, --alpha=
*NUM* Set the alpha tuning factor: y = x^(1/3) * alpha, 1 <= alpha <= x^(1/6).

## Advanced Options for Xavier Gourdon’s Algorithm

- --AC
Compute the A + C formulas.

- --B
Compute the B formula.

- --D
Compute the D formula.

- --Phi0
Compute the Phi0 formula.

- --Sigma
Compute the 7 Sigma formulas.

### Tuning factors

The alpha_y and alpha_z tuning factors mainly balance the computation of the A, B, C and D formulas. When alpha_y is decreased but alpha_z is increased then the runtime of the B formula will increase but the runtime of the A, C and D formulas will decrease. For large pi(x) computations with x >= 10^25 you can usually achieve a significant speedup by decreasing alpha_y and increasing alpha_z. For convenience when you increase alpha_z using **--alpha-z**=*NUM* then alpha_y is automatically decreased.

Both the alpha_y and alpha_z tuning factors are also very useful for verifying pi(x) computations. You compute pi(x) twice but for the second computation you use a slightly different alpha_y or alpha_z factor. If the results of both pi(x) computations match then pi(x) has been verified successfully.

- --alpha-y=
*NUM* Set the alpha_y tuning factor: y = x^(1/3) * alpha_y, 1 <= alpha_y <= x^(1/6).

- --alpha-z=
*NUM* Set the alpha_z tuning factor: z = y * alpha_z, 1 <= alpha_z <= x^(1/6).

## Examples

**primecount 1000**

Count the primes <= 1000.

**primecount 1e17 --status**

Count the primes <= 10^17 and print status information.

**primecount 1e15 --threads 1 --time**

Count the primes <= 10^15 using a single thread and print the time elapsed.

## Homepage

## Author

Kim Walisch <kim.walisch@gmail.com>