Category Archives: Number Theory

Finding the SUM OF DIVISORS of a number

Finding the SUM OF DIVISORS of a number. Divisor Summation. Sum of Factors of a Number Problem: Given a number N, we need to print the Sum of Divisors (Proper and Improper). Example : Input : 20 Ans: Improper Summation : 42 Proper Summation: 22 Solution: Here, the main point that need to be understood… Read More »

Euclids GCD Algorithm

Greatest Common Divisor- Euclid’s Algorithm Problem: Given two numbers M and N, find their GCD. Example: M=36  N=48 Answer: 12 Solution: The GCD or Greatest common divisor of two numbers can be calculated using Euclid’s Algorithm for GCD which is given below: while( n is not divisible by m) { rem = n mod m;… Read More »

Chinese Remainder Theorem

Chinese Remainder Theorem (CRT) In its basic form, the Chinese remainder theorem will determine a number n that, when divided by some given divisors, leaves given remainders. For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and… Read More »

Euler Totient Function (Sieve and Brute force)

Euler’s Totient Function (Sieve and Brute force). In number theory, Euler’s totient function (or Euler’s phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.) Thus, if n… Read More »

Segmented Sieve

Segmented Sieve. Let us suppose we are given two integers, lets say M and N, (M<=N<=109). Now, we need to print prime numbers between M and N. Now, you might be thinking that this can be done using the simple Sieve of Eratosthenes. Yes, this can be done using it, but it takes a lot… Read More »

Factorial of Large Numbers (greater than 20)

Factorial of Large Numbers (greater than 20) Factorial (for Numbers <=20) For numbers <=20, the recursive method of calculating factorial is used. The Factorial() function here works by calling itself again and again till the the value parameter of passed becomes 0 or 1, at which stage the function return the answer 1. Here is… Read More »

Number of Trailing Zeros in N factorial

Number of Trailing Zeros in N! Problem : Given an Integer N , we need to print the number of trailing zeros that would be present in N! Example: n=5 Answer: 1 n=101 Answer: 24 Solution: This solution is based on the Prime Factorization of a Number. Lets take an example n=5 5!=5 * 4… Read More »

Modular Exponentiation

Modular Exponentiation (Raising to a Power with a modulus) E.g. To find 1113 mod 53 13 = 8 + 4 + 1   so  1113 = 118+4+1 = 118 * 114 * 111  We can compute successive squares of 11 to obtain 11, 112, 114, 118  and then multiply together 111 * 114 * 118 to… Read More »

Bitwise Sieve of Eratosthenes

Bitwise Sieve of Eratosthenes. In this post, we Implement the Bitwise Sieve of Eratosthenes. This Sieve comes handy when we want to save space and time while printing prime numbers. We will first provide the code and then explain how it works. The code given below calculates Prime Numbers till 100000000 but we only print… Read More »