'\" t
.\"     Title: primecount
.\"    Author: [see the "AUTHOR" section]
.\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
.\"      Date: 02/17/2024
.\"    Manual: \ \&
.\"    Source: \ \&
.\"  Language: English
.\"
.TH "PRIMECOUNT" "1" "02/17/2024" "\ \&" "\ \&"
.\" -----------------------------------------------------------------
.\" * Define some portability stuff
.\" -----------------------------------------------------------------
.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.\" http://bugs.debian.org/507673
.\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html
.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\" -----------------------------------------------------------------
.\" * set default formatting
.\" -----------------------------------------------------------------
.\" disable hyphenation
.nh
.\" disable justification (adjust text to left margin only)
.ad l
.\" -----------------------------------------------------------------
.\" * MAIN CONTENT STARTS HERE *
.\" -----------------------------------------------------------------
.SH "NAME"
primecount \- count prime numbers
.SH "SYNOPSIS"
.sp
\fBprimecount\fR \fIx\fR [\fIoptions\fR]
.SH "DESCRIPTION"
.sp
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\(cqs 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\&.
.SH "OPTIONS"
.PP
\fB\-d, \-\-deleglise\-rivat\fR
.RS 4
Count primes using the Deleglise\-Rivat algorithm\&.
.RE
.PP
\fB\-g, \-\-gourdon\fR
.RS 4
Count primes using Xavier Gourdon\(cqs algorithm (default algorithm)\&.
.RE
.PP
\fB\-l, \-\-legendre\fR
.RS 4
Count primes using Legendre\(cqs formula\&.
.RE
.PP
\fB\-\-lehmer\fR
.RS 4
Count primes using Lehmer\(cqs formula\&.
.RE
.PP
\fB\-\-lmo\fR
.RS 4
Count primes using the Lagarias\-Miller\-Odlyzko algorithm\&.
.RE
.PP
\fB\-m, \-\-meissel\fR
.RS 4
Count primes using Meissel\(cqs formula\&.
.RE
.PP
\fB\-\-Li\fR
.RS 4
Approximate pi(x) using the Eulerian logarithmic integral: Li(x), with Li(x) = li(x) \- li(2)\&.
.RE
.PP
\fB\-\-Li\-inverse\fR
.RS 4
Approximate the nth prime using the inverse Eulerian logarithmic integral: Li^\-1(x)\&.
.RE
.PP
\fB\-n, \-\-nth\-prime\fR
.RS 4
Calculate the nth prime\&.
.RE
.PP
\fB\-p, \-\-primesieve\fR
.RS 4
Count primes using the sieve of Eratosthenes\&.
.RE
.PP
\fB\-\-phi\fR \fIX\fR \fIA\fR
.RS 4
phi(x, a) counts the numbers <= x that are not divisible by any of the first a primes\&.
.RE
.PP
\fB\-R, \-\-RiemannR\fR
.RS 4
Approximate pi(x) using the Riemann R function: R(x)\&.
.RE
.PP
\fB\-\-RiemannR\-inverse\fR
.RS 4
Approximate the nth prime using the inverse Riemann R function: R^\-1(x)\&.
.RE
.PP
\fB\-s, \-\-status\fR[=\fINUM\fR]
.RS 4
Show the computation progress e\&.g\&. 1%, 2%, 3%, \&... Show
\fINUM\fR
digits after the decimal point:
\fB\-\-status=1\fR
prints 99\&.9%\&.
.RE
.PP
\fB\-\-test\fR
.RS 4
Run various correctness tests and exit\&.
.RE
.PP
\fB\-\-time\fR
.RS 4
Print the time elapsed in seconds\&.
.RE
.PP
\fB\-t, \-\-threads\fR=\fINUM\fR
.RS 4
Set the number of threads, 1 <=
\fINUM\fR
<= CPU cores\&. By default primecount uses all available CPU cores\&.
.RE
.PP
\fB\-v, \-\-version\fR
.RS 4
Print version and license information\&.
.RE
.PP
\fB\-h, \-\-help\fR
.RS 4
Print this help menu\&.
.RE
.SH "ADVANCED OPTIONS FOR THE DELEGLISE\-RIVAT ALGORITHM"
.PP
\fB\-\-P2\fR
.RS 4
Compute the 2nd partial sieve function\&.
.RE
.PP
\fB\-\-S1\fR
.RS 4
Compute the ordinary leaves\&.
.RE
.PP
\fB\-\-S2\-trivial\fR
.RS 4
Compute the trivial special leaves\&.
.RE
.PP
\fB\-\-S2\-easy\fR
.RS 4
Compute the easy special leaves\&.
.RE
.PP
\fB\-\-S2\-hard\fR
.RS 4
Compute the hard special leaves\&.
.RE
.SS "Tuning factor"
.sp
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\&.
.sp
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\&.
.PP
\fB\-a, \-\-alpha\fR=\fINUM\fR
.RS 4
Set the alpha tuning factor: y = x^(1/3) * alpha, 1 <= alpha <= x^(1/6)\&.
.RE
.SH "ADVANCED OPTIONS FOR XAVIER GOURDON\(cqS ALGORITHM"
.PP
\fB\-\-AC\fR
.RS 4
Compute the A + C formulas\&.
.RE
.PP
\fB\-\-B\fR
.RS 4
Compute the B formula\&.
.RE
.PP
\fB\-\-D\fR
.RS 4
Compute the D formula\&.
.RE
.PP
\fB\-\-Phi0\fR
.RS 4
Compute the Phi0 formula\&.
.RE
.PP
\fB\-\-Sigma\fR
.RS 4
Compute the 7 Sigma formulas\&.
.RE
.SS "Tuning factors"
.sp
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 \fB\-\-alpha\-z\fR=\fINUM\fR then alpha_y is automatically decreased\&.
.sp
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\&.
.PP
\fB\-\-alpha\-y\fR=\fINUM\fR
.RS 4
Set the alpha_y tuning factor: y = x^(1/3) * alpha_y, 1 <= alpha_y <= x^(1/6)\&.
.RE
.PP
\fB\-\-alpha\-z\fR=\fINUM\fR
.RS 4
Set the alpha_z tuning factor: z = y * alpha_z, 1 <= alpha_z <= x^(1/6)\&.
.RE
.SH "EXAMPLES"
.PP
\fBprimecount 1000\fR
.RS 4
Count the primes <= 1000\&.
.RE
.PP
\fBprimecount 1e17 \-\-status\fR
.RS 4
Count the primes <= 10^17 and print status information\&.
.RE
.PP
\fBprimecount 1e15 \-\-threads 1 \-\-time\fR
.RS 4
Count the primes <= 10^15 using a single thread and print the time elapsed\&.
.RE
.SH "HOMEPAGE"
.sp
https://github\&.com/kimwalisch/primecount
.SH "AUTHOR"
.sp
Kim Walisch <kim\&.walisch@gmail\&.com>