{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:37:41Z","timestamp":1776843461384,"version":"3.51.2"},"reference-count":7,"publisher":"American Mathematical Society (AMS)","issue":"213","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Let\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"pi left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>\n                              \u03c0\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\pi (x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    denote the number of primes\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"less-than-or-equal-to x\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mo>\n                              \u2264\n                              \n                            <\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\le x<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Our aim in this paper is to present some refinements of a combinatorial method for computing single values of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"pi left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>\n                              \u03c0\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\pi (x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"pi left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>\n                              \u03c0\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\pi (x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis StartFraction x Superscript 2 slash 3 Baseline Over log squared x EndFraction right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mfrac>\n                              <mml:msup>\n                                <mml:mi>x<\/mml:mi>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mn>2<\/mml:mn>\n                                  <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                    <mml:mo>\/<\/mml:mo>\n                                  <\/mml:mrow>\n                                  <mml:mn>3<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                              <mml:mrow>\n                                <mml:msup>\n                                  <mml:mi>log<\/mml:mi>\n                                  <mml:mn>2<\/mml:mn>\n                                <\/mml:msup>\n                                <mml:mo>\n                                  \u2061\n                                  \n                                <\/mml:mo>\n                                <mml:mi>x<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:mfrac>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(\\frac {x^{2\/3}} {\\log ^2x})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    time and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis x Superscript 1 slash 3 Baseline log cubed x log log x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>x<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mo>\/<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mn>3<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:msup>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(x^{1\/3}\\log ^3x\\log \\log x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    space. The algorithm has been implemented and used to compute\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"pi left-parenthesis 10 Superscript 18 Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>\n                              \u03c0\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>10<\/mml:mn>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mn>18<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\pi (10^{18})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/s0025-5718-96-00674-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"235-245","source":"Crossref","is-referenced-by-count":28,"title":["Computing \ud835\udf0b(\ud835\udc65): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method"],"prefix":"10.1090","volume":"65","author":[{"given":"M.","family":"Deleglise","sequence":"first","affiliation":[]},{"given":"J.","family":"Rivat","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/bf01932967","article-title":"On the number of primes less than a given limit","volume":"12","author":"Bohman, Jan","year":"1972","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"issue":"170","key":"2","doi-asserted-by":"publisher","first-page":"537","DOI":"10.2307\/2007973","article-title":"Computing \ud835\udf0b(\ud835\udc65): the Meissel-Lehmer method","volume":"44","author":"Lagarias, J. C.","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0196-6774(87)90037-X","article-title":"Computing \ud835\udf0b(\ud835\udc65): an analytic method","volume":"8","author":"Lagarias, J. C.","year":"1987","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"E. D. F. Meissel, \u00dcber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen, Math. Ann. 2 (1870), 636\u2013642.","DOI":"10.1007\/BF01444045"},{"key":"5","doi-asserted-by":"crossref","unstructured":"\\bysame, Berechnung der Menge von Primzahlen, welche innerhalb der ersten hundert Millionen nat\u00fcrlicher Zahlen vorkommen, Math. Ann. 3 (1871), 523\u2013525.","DOI":"10.1007\/BF01442832"},{"key":"6","doi-asserted-by":"crossref","unstructured":"\\bysame, \u00dcber Primzahlenmengen, Math. Ann. 21 (1883), 304.","DOI":"10.1007\/BF01442926"},{"key":"7","doi-asserted-by":"crossref","unstructured":"\\bysame, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde nat\u00fcrlicher Zahlen vorkommen, Math. Ann. 25 (1885), 289\u2013292.","DOI":"10.1007\/BF01446409"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00674-6\/S0025-5718-96-00674-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00674-6\/S0025-5718-96-00674-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:02:06Z","timestamp":1776718926000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00674-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":7,"journal-issue":{"issue":"213","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["S0025-5718-96-00674-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00674-6","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}