Hello. My name is Ilia Stepanov. This part of our course has been created in joint work with Oleg Hristenko. We will now discuss the basics of number theory. In this lecture, we will talk about integer datatypes in existing programming languages. The limitations of this types and ways to pass those limitations in competitive programming tasks. We will also touch the topic of prime numbers in number theory. Integer variables are one of the core datatypes in existing programming languages. But in fact, it is easy to see that it is impossible to represent integers as they are defined in mathematics. The number of states of any computer is finite. We can enumerate those states by sequential integers between one and N inclusively, where N is some integer. But the integer n plus one exists, and because we enumerated all the states of the computer, this number cannot be represented by any new state. At least two of the first n plus one integers will have the same representation. The axiom N plus one is greater than m cannot be fully implemented in the computer. If for some value X of integer type inequality X plus one is greater than X is not held, such situation is called the integer overflow. To learn when and where the integer overflow may appear, consider how the integer datatypes are implemented. The core integer datatypes usually have size of 1, 2, 4 or 8 bytes, depending on the compiler. Some programming languages like Java, Kotlin, or Python contain built in long integers, but the speed of long integers processing decreases when the length of those integers increases. To understand the reason, consider a long multiplication of N byte integers using a standard algorithm you learned at middle school. You can see the number of distinct values for the core datatypes in C, C++. The maximum unsigned integer consisting of n bytes is stored as the digit one repeated 8N times. But what will happen if we increment this integer? The result is two to the power of 8N. It will have a binary representation in the form leading one followed by 8N zeroes. But we only have 8N binary digits, so there is no place for the 8N plus first digit. Thus, leading one is lost and in fact, the results will be equal to zero. This is how the integer overflow works. After the overflow, we have already lost some data, so the result of the calculations is already incorrect. The values for 8N byte unsigned datatype vary from zero to two to the power of 8N minus one. To introduce the signed integers, consider that minus X is the root of the equation, minus X plus X equals zero. But we can see that X plus two to the power of 8N minus X is equal to two to the power of 8N. We know that two to the power of 8N is represented in the N-byte integer datatype as the zero due to integer overflow. We can use this bug as a feature for the negative integers, numbers 1, 2, et cetera, until two to the power of 8N minus one, minus one, are positive. While numbers two to the power of 8N minus one, plus one until two to the power of 8N minus one, are negative, increasing from minus two to the power of 8N minus one, minus one, two minus one. We have two integers without a pair, zero and two to the power of 8N minus one. The zero remains as zero, and we shall choose the sign for two to the power of 8N minus one. If this number will be considered negative, that is, minus two to the power of 8N minus one, then all the integers with high bit equal to one are considered negative and all the integers with high bit equal to zero are positive. This allows us to implement extremely fast check for the sign. The values for N-byte signed datatype vary from minus two to the power of 8N minus one to two to the power of 8N minus one, minus one inclusively. You can see the maximum and minimum values for the core datatypes. Often, the integer overflow can be avoided by a wide selection of the core datatype for the variable. Note that you will consider not only final values of the variables, but also the intermediate values as well. The result may look relatively small but to calculate this result, numbers which require the biggest coordinates the type to keep, maybe used. Nevertheless, even the 8-byte integer datatype may not be enough for the calculations. For example, if you need to calculate 2020 to the power of 2020, or calculate the 2020th Fibonacci number. Very often in programming contests, you will calculate the answer for the big input data to cut off ineffective solutions. We need to implement some ways to keep the correct answer, avoiding the overflow. The easiest way will be just to ignore the overflow, working with the last eight bytes. But then math is broken even more. For example, in math, we have that A multiplied by B equal 0, implies A equal 0 or B equals 0. But in N-byte integer, the equation has non-trivial solutions. For example, 2 to the power of 4_n plus 1, and 2 to the power of 4_n minus 1. We have two non-zero integers, and the product of those integers is equal to 0. So we need something more stable. One of the ways to deal with the overflow is to print the remainder of division of answer by some integer p, or shortly, print the answer modular p. In most cases, a prime is used as the modular, that is an integer which is divisible only by one and by itself. The primes are actively used in modern cryptography, data encoding, et cetera. Let's look how we can work with the primes. To check if an integer n is a prime, formally we will check all the integers between two and n minus 1 inclusively, and test if n is divisible by at least one of those integers. A negative answer implies that n is prime. This gives time complexity [inaudible] Can we solve this task faster? It is easy to see that we can make our solution twice as fast. At the first step, we check if n is divisible by two, and if not, we can check only odd divisors, but it is still [inaudible] To solve it faster than [inaudible] let's prove the next fact. Any non-prime integer X has a divisor greater than one, and not greater than the square root of X. Suppose that it is wrong, then X is a product of P and Q, where one is less than P, and P is less than X, one is less than Q, and Q is less than X, and both P and Q are greater than the square root of X. But then X, which is equal to P multiplied by Q, is greater than the square root of X multiplied by the square root of X. So X is greater than X, which is impossible. At least one of the divisors is not greater than the square root of X. If an integer does not have any divisors not greater than the square root of n, except for one, it is a prime. Then to check if an integer n is prime, we will check all the integer divisors greater than one and not greater than the square root of n, and time complexity is O of square root of n. To find all the primes between 2 and n inclusively, the next algorithm, known as Eratosthenes Sieve, is widely known. At the first step, we create an integer array, S, with length N, filled with zeros. Then we start the loop from two to N. If the i'th integer is equal to 0, then I is considered as a prime. We can label 2_i, 3_i, et cetera, by ones, because they are divisible by I and some other integer greater than one. So they are definitely not prime. If the i'th integer is equal to one, we just skip this integer and go to the next one. When the process stops, the i'th integer will be equal to 0, if and only if, I is a prime. Can we do that faster? The first idea is similar to the one we used when checking if an integer is a prime. There will be no new non-primes after I becomes greater than the square root of N, because all non-primes between two and N have at least one divisor not greater than the square root of N. They will already be labeled while processing the divisor or some width prime divisors. So the big loop will go between two and the biggest integer not greater than the square root of N. The second idea is to start labeling the integers with one in the internal loop, starting not from 2_i, but from i multiplied by i. This is due to the fact that integers, K multiplied by I, where K is less than I, are divisible by an integer K, which is less than I. They already must be labeled. After these two optimizations, the algorithm works with time complexity O of M multiplied by logarithm of logarithm of N. The proof of that is too complicated to be mentioned in this course. You may find it in books related to the number theory. The example code is given on the slide. We can also modify the Sieve, writing some useful information in the array. For example, when labeling an integer at the first time, we can use not 1 but I, the prime that is used for that labeling. It's easy to see that the array will contain 0 for any prime and a minimal prime divisor for any non-prime. Such an array can be used for fast factorization of the integers. To factorize the integer X, we can just take the X'th element of the array, write it in the list of the factors, divide X by this factor, and continue the process till the respective element of the array will be 0. Keep in mind that integer factorization is not such an easy task, so such a solution can be very useful. Today, we looked at integer data types, considered how to select the integer data type appropriately, and learned how to check if an integer is a prime, and how to generate primes not greater than the given one.