Hello. My name is Nikolai Vavilov. In this course, we will learn math concepts and tools essential for competitive programming. Some of these concepts go back to Ancient Greeks. But recently, they turned out to be extremely useful in many applications including cryptography and fast computations. One of such concepts, is the concept of a prime number. Let's start with a definition. A positive number greater than one is called prime, if it cannot be expressed as the product of two positive numbers greater than one. Well, let's look at the first prime numbers. These are 2, 3, 5, 7, 11, 13. Clearly, there is no obvious pattern for those. Two is a prime number, but any even number greater than two, in other words divisible by two, is not prime. Similarly, three is a prime number, but any positive number greater than three and divisible by three is not prime. Recall, that one is not considered to be a prime number by convention. A number greater than one that is not prime is called composite. In other words, a composite number has a nontrivial divisor, a divisor that is greater than one and smaller than the number itself. Clearly, the smallest nontrivial divisor must be prime, for the otherwise, it would have a smaller divisor. Also, it is obvious that a composite number must have a divisor not exceeding the square root of that number, for otherwise, we can always find a smaller divisor. Let's mention some basic facts about primes. A simple but fundamental theorem was established in Euclid's Elements theorem. There are infinitely many prime numbers. Well, in fact, the number of primes not exceeding a natural number n is approximately n over the natural logarithm of n. As a consequence, the k-th prime number approximately equals k times the natural logarithm of k. Another very basic fact, is the fundamental theorem of arithmetic that says that, "Every natural number greater than one can be uniquely expressed as a product of prime numbers, unique up to their order." Well, a simple recipe to find all prime numbers up to a certain number, was also known since antiquity. Such algorithm is called Eratosthenes Sieve. Let's look at an example. Consider all numbers smaller than 50. Let's write the numbers from one to 49, and cross out those that are not primes. Well, the smallest prime is two, but all positive numbers larger than two, divisible by two are not primes. Let's cross them out. The first number that is not crossed out is three. Again, as we know three is a prime number. But all positive numbers greater than three, divisible by three are not primes. So let's cross them out too. Well, the first number that is not crossed out now is five. It is prime as well. But all numbers greater than five divisible by five are not primes. Now we cross them out. We can stop at seven, since seven is the square root of 49. Thus, each composite number smaller than 50 must have a prime divisor not exceeding seven. We'll look at the table and the primes smaller than 50, are the numbers that were not crossed out during the above procedure. Let us write a pseudo code for this algorithm. We have an array of Boolean's Prime that shows whether a given number is prime. We know that one is not prime, so we set the first value to false. All other values are initially set to true. Then we make a loop over all primes i not exceeding the square root of n. In the inner loop, we mark all numbers j divisible by i as not prime. As an optimization, we start with i squared, because the least prime divisor of j is not greater than the square root of j. So the composite numbers less than i squared, had been crossed out earlier. Let us analyze the algorithm Eratosthenes Sieve for time and space required. Space required is easy, it is capital O of n. Actually by bit compression, one can use only one bit per number not one byte. For instance, in C++, all these can be realized by the standard type bit set. Time required is more complicated, but using some math, we can see that this is approximately the sum of n over primes for all primes not exceeding kn, and this sum can be estimated as capital O of n times the logarithm of the logarithm of n. Well, for those who love mathematics, here is some hint how you can get this estimate. First, you use the known estimate for the initial partial sum of the harmonic series. Then you use the celebrated Euler's product.