PRIMECOUNT

Section: (1)
Updated: 12/15/2022
Index Return to Main Contents

NAME

primecount - 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 logarithmic integral.

--Li-inverse

: Approximate the nth prime using 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.

--Ri

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

--Ri-inverse

: Approximate the nth prime using Ri^-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