The combinatorial algorithm for computing pi(x)

2015/03/06 by Douglas B. Staple, Staple, Douglas B.
Computer Science · Mathematics · #11-04 (Secondary) #11N05 (Primary) #11Y16 #Algorithms and Data Compression #Analytic Number Theory Research #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #History and Theory of Mathematics #Number Theory (math.NT) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1503.01839

openalex publication_date 2015/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper describes recent advances in the combinatorial method for\ncomputing \π(x), the number of primes \≤ x. In particular, the memory\nusage has been reduced by a factor of \log x, and modifications for shared-\nand distributed-memory parallelism have been incorporated. The resulting method\ncomputes \π(x) with complexity O(x^2/3log^-2x) in time and\nO(x^1/3log²x) in space. The algorithm has been implemented and\nused to compute \π(10ⁿ) for 1 \≤ n \≤ 26 and \π(2^m) for 1\≤ m\n\≤ 86. The mathematics presented here is consistent with and builds on that\nof previous authors.\n

Related

• An algorithm for the prime-counting function of primes larger than three
• The combinatorial method to compute the sum of the powers of primes
• Computing π(N): An elementary approach in O(√(N)) time
• Computing π(x) Analytically
• A Note on Algorithms for Computing p_n