In the previous article, we’ve seen how we can calculate the prime factorization of a single number. Today, we’ll focus on how we can efficiently find factorization in a range $[1, n]$. If you understand the sieve algorithm to find prime numbers, you’re good to go. In case you don’t know the sieve algorithm,…

## Prime Factorization – The fundamental theorem of arithmetic

The fundamental theorem of arithmatic states that any number greater than $1$ can be represented as a product of primes and this form of represenation is unique. Now we’ll see two proofs which’ll provide you the intuition why this works. Every integer $n, n \gt 1$ is divisible by at least a prime. If $n$ is a prime, then the l…

## Sieve of Eratosthenes – Generate prime numbers

In the last article about prime numbers, I discussed about different types of primilarity test and Trial division method to verify if a number is a prime. If you haven’t read that yet, here is the article, Prime numbers and basic primilarity test. In this article, we’ll focus on sieve of eratosthenes, which helps us to com…

## Prime numbers and basic primilarity test

A prime number is a integer greater than $1$ and has no positive divisors other than $1$ and itself. $1$ is neither prime nor composite. The set of positive integers can be divided into three classes, primes, composites and a unit ($1$). For example, $5$ is prime because the only ways of writing it as a product, $1 Ã— 5$ or $5 Ã— 1$, involve $5$…

## GCD and Euclidean Algorithm

Suppose we have two integers $a$ and $b$. We say that the number $d$ is the greatest common divisor of $a$ and $b$ if and only if, $d | a$ and $d | b$ and if $c | a$ and $c | b$, then $c \leq d$.
Condition $1$ says that $d$ is a common divisor of $a$ and $b$, and condition $2$ says that it is the greatest such divisor. Note that if $a$ and $b$ are not both z…