primecount(1) ============= :doctype: manpage 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':: 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