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)