Counting Primes Quickly with Linnik's Identity



This page provides a description of a novel prime counting algorithm that operates in O(n^2/3 log n) time and O(n^1/3 log n) space, based on Linnik's identity. I worked heavily on developing this approach back in 2011. I've included several attempts at describing the approach in multiple papers below. The first paper is probably the one to read.

  • Prime Counting in O(n^2/3 log n) time and O(n^1/3 log n) space with Linnik's identity

    (PDF, 2011-11-23 ) This is a write up of an algorithm I've put together for counting the number of primes less than some number n, relying on Linnik's identity and properties of the divisor summatory functions. This paper includes both a detailed description of the algorithm as well as a function C implementation that demonstrates its running time properties.

  • A Survey of a Few Novel, Quick Prime Number Counting Techniques

    (PDF, 2012-12-5) This paper presents several prime counting approaches all stemming from Linnik's identity, working from simplest and easiest to understand to the most complex, with the above approach being the final one. It is a survey and is intended to be more descriptive than the terse original paper. It includes both Mathematica and C code for most of the approaches .

  • Extending My Prime Counting Algorithm to Computing the Sums of Primes

    (PDF, 2011-11-23) My prime counting algorithm generalizes to compute any non-negative integer prime sums in O(n^2/3 log n) time and O(n^1/3 log n) space. This is an informal and rough write-up of how such an algorithm works. A rough implementation of this idea (with some shaky precision issues) can be found here.

  • Earlies Writeup of Assorted Results Connected to Linnik's Identity

    (PDF, 2011-3-24) This is my original, overly long, unfocused document where I first wrote up this algorithm, mixed in with a bunch of other unrelated results. This is the document linked to by oeis.org, but it's probably not the best choice for following my results.