Number Theory

Number Theory is concerned mainly with the study of properties of positive integers. Problems in competitive programming involving Maths are usually based on number theory. If we know number theory, it increases our ability to solve more challenging problems, clears our concepts, and helps us get a solid hold on programming.

Basics

Number theory involves various types of integers like prime numbers, composite numbers, and the relation between them. Base numbers and arithmetics numbers are also the topics involved in number theory. Following are some fundamental number theory problems every programmer should be well aware of.

Prime Numbers

An elementary math concept, those numbers which have only 2 factors, the number itself and 1 are called Prime Numbers.
Let's discuss more the same!

Combinatorics

Combinatorics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system.
In thi

Common Problems

The basic topics that come under Number Theory are Prime Numbers, GCD, Extended Euclid Algorithm, Modular Arithmetic, etc. Questions from these topics

Advanced

The advanced topics that come under Number Theory are Modular Exponentiation, Fermat's Little Theorem, Wilson's Theorem, Chinese Remainder Theorem, Euler Totient Function, Matrix Exponentiation, etc. Questions from these topics are not much asked in the interviews of Top Product-Based Companies. But, if you are a Competitive Programming enthusiast you must cover these topics.

Counting Triangles in a Rectangular space using BIT

By Jaglike Makkar

● Published At Feb 2022

In this article, we will discuss the approach to count the number of triangles that can be formed by connecting the points inside a rectangle for multiple queries. We will also focus on the complexity of our approach.... Keep reading ..

Karatsuba Algorithm for fast multiplication of large decimal numbers represented as strings

By SHIKHAR SONI

● Published At Jan 2022

This article discusses the Karatsuba algorithm, its intuition and C++ code... Keep reading ..

Find the remainder when a number A raised to N factorial is divided by P

By Urwashi Priya

● Published At Jan 2022

This article will brief you on the problem to find the remainder when a number A raised to N factorial is divided by P.... Keep reading ..

The Number of Unordered Pairs of Semiprime Numbers with a Prime Sum in the Range 1 to N

By GAZAL ARORA

● Published At Mar 2022

In this article, we will design an algorithm for counting the number of unordered pairs of semiprime numbers in the range [1, N], whose sum is a prime number.
... Keep reading ..

Count the permutations of first N positive integers such that the sum of any two consecutive numbers is prime

By Ayush Prakash

● Published At Feb 2022

In this blog, we will discuss the problem: Count the permutations of first N positive integers such that the sum of any two consecutive numbers is prime. We will also discuss the time and space complexity of the approach discussed.
... Keep reading ..

Count the Possible Sets Using Integers from a Range [2, N] Using Given Operations that are in Equivalence Relation

By Soumya Agrawal

● Published At Mar 2022

This article will cover the problem Count of Sets Possible using Integers from a Range[2, N] using Given Operations in Equivalence Relation and its implementation.... Keep reading ..

Count of sorted triplets (a, b, c) whose product is at most equal to N

By Vibhor Bhatnagar

● Published At Jan 2022

In this article, we will discuss the problem to count of sorted triplets (a, b, c) whose product is at most equal to N.
... Keep reading ..

Count of Arrays of Size N that can be Formed Starting With K Such that Every Element is Divisible by the Next Element

By GAZAL ARORA

● Published At Mar 2022

In this article, we will design an algorithm for counting the number of the N-sized arrays that can be formed starting with K such that every element is divisible by the next element.... Keep reading ..

Count of Numbers in Range [L, R] having Sum of Digits of its Square Equal to Square of Sum of Digits

By Malay Gain

● Published At Mar 2022

In this article, we will learn how to count of numbers in range [L, R] having sum of digits of its square equal to square of sum of digits.... Keep reading ..

Find the number formed by K times, alternatively reducing X and adding Y to 0

By Urwashi Priya

● Published At Jan 2022

This article will brief you on the problem to Find the number formed by K times, alternatively reducing X and adding Y to 0.
... Keep reading ..

Fermat’s Factorization Method

By Husen Kagdi

● Published At Oct 2021

This blog discusses Fermat’s factorization method for breaking a number into its factors. This is a very useful method to find factors of a number.... Keep reading ..

Chinese remainder theorem

By Pradipta Choudhury

● Published At Dec 2021

The article covers the Chinese remainder theorem, its working with hands-on examples, and its implementation with a naive and efficient approach.
... Keep reading ..

Euclidean Algorithm

By Nishant Rana

● Published At Dec 2021

This blog will cover the theory, implementation, and discussion over the Time and Space complexity of the Extended Euclidean Algorithm.... Keep reading ..

Multiplicative Inverse

By Pradipta Choudhury

● Published At Dec 2021

In this article, we will learn how to find the modular multiplicative inverse of a number ‘a’ under ‘m’, learn how to implement it, starting from a naive to an efficient approach. ... Keep reading ..

Factorial Modulo

By Sneha Mallik

● Published At Oct 2021

This blog covers the concepts for understanding factorial modulo with ease, its implementation and algorithm.... Keep reading ..

Binary Exponentiation

By Harsh Goyal

● Published At Oct 2021

This article will discuss the Binary Exponentiation algorithm and various ways to use it to solve coding problems efficiently.
... Keep reading ..

Find the Missing Digit in Given Product of Large Positive Integers

By Abhishek Ranjan

● Published At Mar 2022

In this article, we will solve a number theory problem that can be asked in the interviews.... Keep reading ..

Count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices

By Vibhor Bhatnagar

● Published At Jan 2022

This article will discuss the problem to get the count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices.... Keep reading ..

Largest subset with a composite sum

By SHIKHAR SONI

● Published At Jan 2022

This article discusses the approach and C++ code to find the largest subset with a composite sum... Keep reading ..

## Top Problems related to Number Theory

Yogesh And Primes

Check If Given Numbers Are Coprime

Check Integer Overflow

Distribute Items

Convert Decimal To Irreducible Fraction

Nearest Multiple of 10

Successor Problem

Day of the Week

Gas Tank

N-th Term Of GP

Mean Median Mode

Decimal to Octal Conversion

Nth Element Of Modified Fibonacci Series

Euler’s Totient Function

Find prime numbers

Trailing Zeros in Factorial

Climbing the leaderboard

Prime Time Again

Closest greater

Shopping Spree

Max GCD Pair