Introduction to Combinatorics (Part 1)

Combinatorics is a branch of mathematics which is about counting. Here we are concerned with problems like number of ways to select/arrange something. These types of combinatorial problems have attracted the attention of mathematicians since early times. In this post, we’ll pick some problems and try to answer them using combinatorics. Q1: How many 3 […]

Prime Factorization using Sieve Method

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, you […]

The Unique Prime Factorization Theorem

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. Remember factoring integers in grade school? That’s exactly what we’re talking about. Now we’ll see two proofs which’ll provide you the intuition why this works. Every integer n, […]

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 […]

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 […]