Hi,

Our last topic stream was on Number Theory. I will continue discussing number theory next week, where we will cover more facts and solve more problems.

Here is the text version of this topic stream. I will briefly summarize all the topics discussed in the livestream. You can watch the full session below.

Definition of GCD

In this section, I introduce the concept of the Greatest Common Divisor.

Proving that gcd(a, b) = gcd(a — b, b)

As the title suggests, we prove a fact about GCD. This fact is extremely useful!

The Naive Algorithm to Calculate GCD

Here, we introduce the naive solution to calculate the GCD. It works in O(min(a, b)) by simply iterating through all possible candidates.

Extend the Fact to gcd(a, b) = gcd(a % b, b)

Then, we extend the fact that gcd(a, b) = gcd(a — b, b) to gcd(a, b) = gcd(a % b, b).

Prove that a % b < a / 2 if a >= b

In this section, we prove another very useful fact, which helps us find the GCD with improved time complexity.

O(lg a) Algorithm to Calculate GCD

Here, we use the facts to improve our solution to calculate the gcd of two numbers.

Solving 1458A from Codeforces

In this section, the following problem will be solved. It is really beautiful.

https://mirror.codeforces.com/problemset/problem/1458/A

How to Find All the Prime Numbers between 1 and N in O(N)

Another classic problem in number theory.

Improving the Algorithm to O(N sqrt(N))

We use a simple fact to reduce one N to sqrt(N).

Sieve of Eratosthenes — Improving the Algorithm to O(N.lgN)

Here, I introduce the Sieve of Eratosthenes. I explain the solution step by step, and at the end, I mention that this method is called the Sieve of Eratosthenes.

Harmonic Series

In the middle of solving the problem with this method, we encounter with a number that we have to find out how big it is. We need this to find out the time complexity of our method. We will analyze the complexity of this number. We will analyze the complexity of this number, and we’ll see that it is actually known as the Harmonic Series.

Solving 230B from Codeforces

Then, we try to use the topics we talked about to solve the following problem from Codeforces.

https://mirror.codeforces.com/problemset/problem/230/B

Find the Smallest Prime Factor with Sieve

Actually, Sieve can be used to solve more challenging problems as well. Here, we discuss how to find the smallest prime factor of a number using Sieve.