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)

The number theoretic functions equipped with Dirichlet convolution and prefix sum, form one of the most important topics in elementary number theory.In this text, we are going to study the number theoretic functions, however this is done from algebraic perspective by studying the Dirichlet ring, which they form under addition and Dirichlet convolution.Actually, one who gets the chance to study both elementary number theory and algebra in parallel will find how convenience and simple it is by...(read more)

For two integers and , their greatest common divisor is the greatest number such that . Otherwise we could take such that is the common divisor of but is greater than , which is a contradiction to our previous definition.When evaluating greatest common divisor between and...(read more)