An algorithm for the prime-counting function of primes larger than three

2020/02/28 by Yuri Heymann, Heymann, Yuri
Mathematics · #Advanced Mathematical Identities #Analytic Number Theory Research #FOS: Mathematics #General Mathematics (math.GM) #History and Theory of Mathematics

paper · pdf · doi:10.48550/arxiv.2002.12797

openalex publication_date 2020/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The prime-counting function π(x) which computes the number of primes smaller or equal to a given real number has a long-standing interest in number theory. The present manuscript proposes a method to compute π(x) with time complexity O(x^1/2) without the need to introduce the non-trivial zeros of the Riemann zeta function.

Citations

• On Riemann's Paper, "On the Number of Primes Less Than a Given Magnitude"
• Computing π(x) Analytically

Related

• Computing π(x) Analytically
• Computing π(N): An elementary approach in O(√(N)) time
• A Note on Algorithms for Computing p_n
• An algorithmic implementation of the Pi function based on a new sieve
• New bounds for the prime counting function π(x)