PRIMECOUNT(1) PRIMECOUNT(1)
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 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
https://github.com/kimwalisch/primecount
AUTHOR
Kim Walisch
02/17/2024 PRIMECOUNT(1)