With the elementary knowledge about distribution of prime numbers, we are finally able to characterize the time complexity of different prime number sieves precisely. This will help us reasonably understand and argue about our improvement of prime number sieve over the classical Eratosthenes sieve.All of us might be very familiar with the sieve of Eratosthenes: to sieve the primes below , we keep a bitset and scan integers from to ; if...(read more)

Prime number theorem, which claims the number of primes below is asymptotically equal to , is one of the most important concept developed by mathematicians, nevertheless a flex of its muscle of the analytic number theory.Besides a non-trivial distribution rule of prime numbers, the prime number theorem is actually a bridge of enormous analytic method applied to number theory, which we will see in the following texts.In this text, we will first introduce...(read more)

When establishing the size of certain problems and the time complexity of certain algorithms, especially for those closely related to number theory, a skirmish with number theoretic functions and their prefix sums may be inevitable. They are in staircase shape, some of them are hard to visualize or calculate directly, while precise calculation is unnecessary when we just want to estimate the size or complexity.And this is how the natural idea of asymptotic...(read more)