Math Tricks in Competitive Programming

by

Competitive programming is not just about knowing programming syntax—it’s a blend of logic, speed, and mathematics. Mastering a few essential math tricks can drastically boost your problem-solving skills and efficiency.

Let’s explore the most powerful and commonly used math techniques in competitive programming.

Prime Numbers

A prime number is a number greater than 1 that has no positive divisors other than 1 and itself.

Example: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

Naive Primality Test

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
Python

  • Time complexity: O(n)
  • Too slow for large numbers (n up to 10⁶ or 10⁹).

Checking upto √n

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            return False
    return True
Python

  • Time complexity: O(√n)

Why √n

If a number n is not prime, then it can be written as n = a * b

where a and b are integers greater than 1.

Case 1 : If both a and b were greater than √n,

a = √n+x 

b = √n+y 

so, a * b = (√n+x)*(√n+y) = n + z 

then, n < a*b

That's impossible if a × b = n
Python

Case 2 If both a and b were less than √n,

a = √n-x 

b = √n-y 

so, a * b = (√n-x)*(√n-y) = n - z 

then, n > a*b

That's impossible if a × b = n
Python

Conclusion

From case 1 and case 2: So, at least one of them must be ≤ √n.

Example 1: n = 36 , while √n = 6

aba × b
13636
21836
31236
4936
6636
9436
12336
18236
36136

Example 2: n = 18 √18 ≈4.24

aba × b
11818
2918
3618
6318
9218
18118

Summary

If n = a × b, then either a ≤ √n or b ≤ √n.

That’s why:

  • You only check up to √n.
  • After that, divisors start repeating in reverse order.

Optimized Primality Test (using √n)

import math
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.isqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True
Python

  • To reduce the set of candidate numbers, we directly checking for 2,3
  • left overs are 5,7,11,13,17,19,23,29
  • Basic idea — all primes > 3 are of the form 6k ± 1
  • Also note n % i == 0 or n % (i + 2) == 0, will discussion this in future articles.

So, for any number greater than 3: The only candidates for primes are 6k ± 1, i.e.,

Could we go beyond 6?

Yes, you can generalise this idea further

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an efficient algorithm to find all primes ≤ n by systematically eliminating multiples of primes.

So, instead of checking each number for primality one by one (which is slow), we eliminate multiples of known primes. “If a number is prime, all its multiples are composite.

A composite number is a positive integer greater than 1 that is not prime meaning it has more than two positive divisors.

i.e.

  • If p is prime, then 2p, 3p, 4p, … are all composite.
  • The number p itself is not composite — it’s prime.
  • Example 5 prime, and 10,15,20 are composite

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False

    return [i for i in range(2, n + 1) if is_prime[i]]
Python

  • Time complexity: O(n log log n)
  • Space: O(n)

We are using i*i, because all smaller multiples have already been marked by smaller primes.

Example : Finding all prime numbers up to 30 using the Sieve of Eratosthenes

Step 1: Write down numbers from 2 to 30
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30


Step 2: Start with 2 (smallest prime)
2 is prime, so we keep 2 and cross out all its multiples:
✅ 2, 3, ❌4, 5, ❌6, 7, ❌8, 9, ❌10, 11, ❌12, 13, ❌14, 15, ❌16, 17, ❌18, 19, ❌20, 21, 
❌22, 23, ❌24, 25, ❌26, 27, ❌28, 29, ❌30


Step 3: Next unmarked number → 3
✅ 2, ✅3, ❌4, ✅5, ❌6, ✅7, ❌8, ❌9, ❌10, ✅11, ❌12, ✅13, ❌14, ❌15, ❌16, ✅17, ❌18,
✅19, ❌20, ❌21, ❌22, ✅23, ❌24, ❌25, ❌26, ❌27, ❌28, ✅29, ❌30


Step 4: Next unmarked number → 5
5 is prime, so keep it and cross all multiples of 5:

✅ 2, ✅3, ❌4, ✅5, ❌6, ✅7, ❌8, ❌9, ❌10,✅11, ❌12, ✅13, ❌14, ❌15, ❌16, ✅17, ❌18,
✅19, ❌20, ❌21, ❌22, ✅23, ❌24, ❌25, ❌26, ❌27, ❌28, ✅29, ❌30



Step 5: Stop when p > √30
√30 ≈ 5.47, so we stop after 5

Step 6: Collect all numbers still marked as prime
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Python

Golden Statement

To check if a number n is prime, you only need to test divisibility by prime numbers ≤ √n

Why this works:

Factor Pairs: If n has a composite divisor, it must also have a corresponding factor. If n = a × b where a > √n, then b < √n. So checking up to √n is sufficient.

Prime Divisors Only: If n is divisible by a composite number c, then n is also divisible by the prime factors of c. Since we’re looking for any divisor, we only need to check primes.

Segmented Sieve

If you’re asked to find all primes in a given range [L, R], and R can be very large (say 10^12) you can’t use the normal Sieve of Eratosthenes because it requires O(R) memory.

Solution

We don’t sieve up to R directly. Instead, we:

  • Generate all base primes up to √R (using normal sieve).
  • Use these base primes to mark multiples in the range [L, R].
  • Thus, we only need memory for range size = (R − L + 1), which is much smaller than R.

The common confusion: Segmented Sieve we use sieve(), and is’nt there we require memory of size R

  • We don’t run the normal sieve up to R.
  • We run it only up to √R, which is tiny in comparison.

Code

import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False

    return [i for i in range(2, n + 1) if is_prime[i]]


def segmented_sieve(L, R):
    """Find all primes in the range [L, R] using your sieve() as base."""
    
    # Step 1: Find all base primes up to sqrt(R)
    limit = int(math.sqrt(R)) + 1
    base_primes = sieve(limit)
    
    # Step 2: Assume all numbers in [L, R] are prime
    is_prime_range = [True] * (R - L + 1)
    
    # Step 3: Mark non-primes using base primes
    for p in base_primes:
        # Find the first multiple of p within [L, R]
        start = max(p * p, ((L + p - 1) // p) * p)
        
        for j in range(start, R + 1, p):
            is_prime_range[j - L] = False
    
    # Step 4: Handle edge case when L = 1
    if L == 1:
        is_prime_range[0] = False
    
    # Step 5: Collect all primes
    primes_in_range = [L + i for i, val in enumerate(is_prime_range) if val]
    return primes_in_range


# -------------------------------
# Example Usage
# -------------------------------
if __name__ == "__main__":
    L = 10
    R = 50
    primes = segmented_sieve(L, R)
    print(f"Primes in range [{L}, {R}]: {primes}")
Python

Prime Factors

Prime factors of a number are the prime numbers that multiply together to give the original number.

Example

  • 12 = 2 * 2 * 3 –> Prime factors = [2, 2, 3]
  • 30 = 2* 3 * 5 –> Prime factors = [2, 2, 5]

Trial division algorithm

def prime_factors(n):
    factors = []      # list to store prime factors
    i = 2             # start dividing from 2 (the first prime)

    # loop until i*i <= n
    while i * i <= n:
        # if i divides n, it's a factor
        while n % i == 0:
            factors.append(i)   # store the factor
            n //= i             # divide n by i to reduce it
        i += 1                  # move to next number

    # if n is still greater than 1, it is itself a prime
    if n > 1:
        factors.append(n)

    return factors
Python

Time Complexity

  • Roughly O(√n), because we only check divisors up to √n.

Optimized using Precomputed Primes

You can use primes from Sieve up to √n instead of all numbers.

Smallest Prime Factor (SPF) Sieve

The Smallest Prime Factor (SPF) Sieve is a modified version of the Sieve of Eratosthenes.

It doesn’t just tell you whether a number is prime – it also tells you the smallest prime that divides each number.

i.e its Smallest Prime Factor (SPF) is the smallest prime number that divides a number.

Example

nPrime factorsSPF
222
333
42×22
62×32
93×33
102×52
497×77

Precompute smallest prime divisor for every number.

def spf_sieve(n):
    spf = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, n + 1, i):
                spf[j] = min(spf[j], i)
    return spf
Python

Then factorization in O(log n):

def factorize(n, spf):
    factors = []
    while n != 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors
Python

Number of times a prime p exist in n!

count_of_p = n//p + n//p^2 + n//p^3........
Python

Example find no. of trailing zero in 100!

  • Zero is formed by 2*5
no_of_2 = 100/2 +100//4 + 100//8 + 100/16 + 100/32 + 100/64 + 100/128
        = 50 + 25 + 12 + 6 + 3 + 1 + 0 .....
        = 97
Python

no_of_5 = 100//5 + 100//25 + 100//125
        = 20 + 4 + 0
        = 24
Python

So, no of zero min(no_of_2,no_of_5) = 24

Compute: a^b

Naive Method:

def power(a, b):
    result = 1
    for _ in range(b):
        result *= a
    return result
Python

  • Multiplying a , b times
  • It become, inefficient especially when b is large.
  • Time Complexity: O(b) => O(n)

Fast Exponentiation Idea

Reduce the number of multiplications by squaring instead of multiplying a again and again.

Example: a^8

  • a^8 = (a^4)^2 = ((a^2)^2)^2
  • Instead of multiplying a 8 times, you just square 3 times!

2^10 => 4^5 => 
4^5 => 4^(4+1) => 16^2 * 4^1
Python

  • Using above representation of the exponent, it reduces the time to O(log b).

Code

def fast_pow(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:      # if current bit is 1
            result *= a
        a *= a              # square the base
        b //= 2             # move to next bit
    return result
Python

Key concept:

  • In every loop we square ‘a‘ (a^2) while reduces b by half
  • When b is odd, we multiple ‘a’ once

Special case b is negative

def fast_pow(a, b):
    if b == 0:
        return 1
    if b < 0:
        return 1 / fast_pow(a, -b)  # invert the result

    result = 1
    while b > 0:
        if b % 2 == 1:
            result = result * a
        a = a * a
        b = b // 2
    return result
Python

Note :

  • 1 / fast_pow(a, -b), we passing -b
  • a^(-b) = 1 / (a^b)
  • Example 2^(-3) = 1 / (2^3) = 1 / 8 = 0.125

Why This Is Better Than a Loop:

  • A regular loop takes b steps.
  • Fast exponentiation takes only log₂(b) steps.

For example:

  • If b = 1_000_000_000, loop = 1 billion steps
  • Fast exponentiation = only 30 steps

Practice

Logarithm

Definition: bc = a ⇔ logb(a) = c

Log of 1: logb(1) = 0 ⇔ b0 = 1

Log of base: logb(b) = 1 ⇔ b1 = b

Log of power: logb(an) = n · logb(a)

Product Rule: logb(x · y) = logb(x) + logb(y)

Quotient Rule: logb(x / y) = logb(x) – logb(y)

Change of Base: logb(x) = logk(x) / logk(b) [for any base k>0]

Number of digits

Count number of digits in base 10:

  • Number of digits of n = ⌊log10(n)⌋ + 1
  • Valid when n>0

Count number of digits in binary

  • Number of digits of n = ⌊log2(n)⌋ + 1
  • This tells how many bits are needed to represent n in binary.

import math
n = 123456
digits = math.floor(math.log10(n)) + 1 #output 6



import math
n = 18   #10010
bits = math.floor(math.log2(n)) + 1  # Output: 5
Python

Why does this works?

Every time you multiply by 10, you add a digit:

NumberDigitslog10(n)⌊log10(n)⌋ + 1
91~0.951
1021.02
992~1.992
10032.03
9993~2.993
100043.04

Leave a Comment