{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T22:10:05Z","timestamp":1748815805832,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_15","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"192-206","source":"Crossref","is-referenced-by-count":1,"title":["The I\/O Complexity of Computing Prime Tables"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Rezaul","family":"Chowdhury","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Conway","sequence":"additional","affiliation":[]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[]},{"given":"Pramod","family":"Ganapathi","sequence":"additional","affiliation":[]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[]},{"given":"Bertrand","family":"Simon","sequence":"additional","affiliation":[]},{"given":"Shikha","family":"Singh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"issue":"9","key":"15_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, S.: Jeffrey: the input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"50","author":"M Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Ann. Math. 50, 781\u2013793 (2004)","journal-title":"Ann. Math."},{"issue":"1","key":"15_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","volume":"37","author":"L Arge","year":"2003","unstructured":"Arge, L.: The buffer tree: a technique for designing batched external data structures. Algorithmica 37(1), 1\u201324 (2003)","journal-title":"Algorithmica"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: Cache-oblivious priority queue and graph algorithm applications. In: Proceedings of the 34th Annual Symposium on Theory of Computing, pp. 268\u2013276 (2002)","DOI":"10.1145\/509907.509950"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-642-45030-3_46","volume-title":"Algorithms and Computation","author":"L Arge","year":"2013","unstructured":"Arge, L., Thorup, M.: RAM-efficient external memory sorting. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 491\u2013501. Springer, Heidelberg (2013)"},{"issue":"246","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1090\/S0025-5718-03-01501-1","volume":"73","author":"A Atkin","year":"2004","unstructured":"Atkin, A., Bernstein, D.: Prime sieves using binary quadratic forms. Math. Comput. 73(246), 1023\u20131030 (2004)","journal-title":"Math. Comput."},{"issue":"2","key":"15_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01932283","volume":"17","author":"C Bays","year":"1977","unstructured":"Bays, C., Hudson, R.H.: The segmented sieve of Eratosthenes and primes in arithmetic progressions to 1012. BIT Numer. Math. 17(2), 121\u2013127 (1977)","journal-title":"BIT Numer. Math."},{"issue":"2","key":"15_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF00289493","volume":"23","author":"S Bengelloun","year":"1986","unstructured":"Bengelloun, S.: An incremental primal sieve. Acta Informatica 23(2), 119\u2013125 (1986)","journal-title":"Acta Informatica"},{"issue":"124","key":"15_CR9","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1090\/S0025-5718-1973-0330021-0","volume":"27","author":"RP Brent","year":"1973","unstructured":"Brent, R.P.: The first occurrence of large gaps between successive primes. Math. Comput. 27(124), 959\u2013963 (1973)","journal-title":"Math. Comput."},{"key":"15_CR10","volume-title":"Primes of the Form $$x^2+ny^2$$","author":"DA Cox","year":"1989","unstructured":"Cox, D.A.: Primes of the Form $$x^2+ny^2$$ x 2 + n y 2 : Fermat, Class Field Theory, and Complex Multiplication. Wiley, New York (1989)"},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0020-0190(96)00099-3","volume":"59","author":"B Dunten","year":"1996","unstructured":"Dunten, B., Jones, J., Sorenson, J.: A space-efficient fast prime number sieve. IPL 59(2), 79\u201384 (1996)","journal-title":"IPL"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-662-48971-0_57","volume-title":"Algorithms and Computation","author":"M Farach-Colton","year":"2015","unstructured":"Farach-Colton, M., Tsai, M.-T.: On the complexity of computing prime tables. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 677\u2013688. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48971-0_57"},{"key":"15_CR13","volume-title":"CGOL-an Algebraic Notation for MACLISP Users","author":"R Gale","year":"1977","unstructured":"Gale, R., Pratt, V.: CGOL-an Algebraic Notation for MACLISP Users. MIT Artificial Intelligence Library, Cambridge (1977)"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/10722028_17","volume-title":"Algorithmic Number Theory","author":"WF Galway","year":"2000","unstructured":"Galway, W.F.: Dissecting a sieve to cut its need for space. In: Bosma, W. (ed.) ANTS-IV. LNCS, vol. 1838, pp. 297\u2013312. Springer, Heidelberg (2000)"},{"issue":"12","key":"15_CR15","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1145\/359657.359660","volume":"21","author":"D Gries","year":"1978","unstructured":"Gries, D., Misra, J.: A linear sieve algorithm for finding prime numbers. Commun. ACM 21(12), 999\u20131003 (1978)","journal-title":"Commun. ACM"},{"key":"15_CR16","volume-title":"An Introduction to the Theory of Numbers","author":"GH Hardy","year":"1979","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford University Press, Oxford (1979)"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1098\/rstl.1772.0023","volume":"62","author":"S Horsley","year":"1772","unstructured":"Horsley, S.: KO $$\\Sigma $$ \u03a3 KINON EPATO $$\\Sigma \\Theta $$ \u03a3 \u0398 ENOY $$\\Sigma $$ \u03a3 . or, the sieve of eratosthenes. being an account of his method of finding all the prime numbers, by the Rev. Samuel Horsley, FRS. Philos. Trans. 62, 327\u2013347 (1772)","journal-title":"Philos. Trans."},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-36206-1_1","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"HW Lenstra Jr","year":"2002","unstructured":"Lenstra Jr., H.W.: Primality testing with gaussian periods. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol. 2556, pp. 1\u20131. Springer, Heidelberg (2002)"},{"issue":"9","key":"15_CR19","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/359810.359838","volume":"20","author":"HG Mairson","year":"1977","unstructured":"Mairson, H.G.: Some new upper bounds on the generation of prime numbers. Commun. ACM 20(9), 664\u2013669 (1977)","journal-title":"Commun. ACM"},{"key":"15_CR20","first-page":"46","volume":"78","author":"F Mertens","year":"1874","unstructured":"Mertens, F.: Ein beitrag zur analytischen zahlentheorie. J. fr die reine und angewandte Mathematik 78, 46\u201362 (1874)","journal-title":"J. fr die reine und angewandte Mathematik"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"News, F.: World\u2019s largest prime number discovered - all 17 million digits, February 2013. https:\/\/web.archive.org\/web\/20130205223234\/ , http:\/\/www.foxnews.com\/science\/2013\/02\/05\/worlds-largest-prime-number-discovered\/","DOI":"10.1063\/pt.5.026748"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M., Dynamic integer sets with optimal rank, select, predecessor search. In: FOCS, pp. 166\u2013175 (2014)","DOI":"10.1109\/FOCS.2014.26"},{"issue":"151","key":"15_CR23","first-page":"1003","volume":"35","author":"C Pomerance","year":"1980","unstructured":"Pomerance, C., Selfridge, J.L., Wagstaff, S.S.: The pseudoprimes to $$25 \\cdot 10^9$$ 25 \u00b7 10 9 . Math. Comput. 35(151), 1003\u20131026 (1980)","journal-title":"Math. Comput."},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Pomerance, C., Shparlinski, I.E.: On pseudosquares and pseudopowers. Comb. Number Theor., 171\u2013184 (2009)","DOI":"10.1515\/9783110208504.171"},{"issue":"1","key":"15_CR25","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/358527.358540","volume":"24","author":"P Pritchard","year":"1981","unstructured":"Pritchard, P.: A sublinear additive sieve for finding prime number. Commun. ACM 24(1), 18\u201323 (1981)","journal-title":"Commun. ACM"},{"issue":"4","key":"15_CR26","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF00264164","volume":"17","author":"P Pritchard","year":"1982","unstructured":"Pritchard, P.: Explaining the wheel sieve. Acta Informatica 17(4), 477\u2013485 (1982)","journal-title":"Acta Informatica"},{"issue":"1","key":"15_CR27","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0167-6423(87)90024-4","volume":"9","author":"P Pritchard","year":"1987","unstructured":"Pritchard, P.: Linear prime-number sieves: a family tree. Sci. Comput. Program. 9(1), 17\u201335 (1987)","journal-title":"Sci. Comput. Program."},{"key":"15_CR28","unstructured":"Sch\u00f6nhage, A., Grotefeld, A., Vetter, E.: Fast algorithms: a multitape turing machine implementation. Wissenschaftsverlag, B.I (1994)"},{"key":"15_CR29","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/363235.363247","volume":"12","author":"RC Singleton","year":"1969","unstructured":"Singleton, R.C.: Algorithm 357: an efficient prime number generator. Commun. ACM 12, 563\u2013564 (1969)","journal-title":"Commun. ACM"},{"key":"15_CR30","unstructured":"Sorenson, J.: An introduction to prime number sieves. Technical report 909, Computer Sciences Department, University of Wisconsin-Madison (1990)"},{"key":"15_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/11792086_15","volume-title":"Algorithmic Number Theory","author":"JP Sorenson","year":"2006","unstructured":"Sorenson, J.P.: The pseudosquares prime sieve. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 193\u2013207. Springer, Heidelberg (2006)"},{"key":"15_CR32","unstructured":"Villarino, M.B.: Mertens\u2019 proof of mertens\u2019 theorem. arXiv:math\/0504289 (2005)"},{"issue":"2","key":"15_CR33","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"JS Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. (CsUR) 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv. (CsUR)"},{"key":"15_CR34","unstructured":"Williams, H.C.: Edouard Lucas and primality testing. Canadian Mathematics Society Series of Monographs and Advanced Texts, 22 (1998)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T21:29:22Z","timestamp":1748813362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}