Understanding Mathematical Algorithms

Introduction

Mathematical algorithms are essential building blocks in computer science, competitive programming, cryptography, and optimization. These algorithms help perform operations efficiently on numbers, primes, modular arithmetic, and more.

In this chapter, you will learn the most important mathematical algorithms such as:

• Prime Number Algorithms

• Sieve of Eratosthenes

• Greatest Common Divisor (GCD)

• Least Common Multiple (LCM)

• Modular Arithmetic

• Fast Exponentiation (Binary Exponentiation)

• Modular Inverse

• Factorization

Understanding these will improve your problem-solving skills and prepare you for advanced topics.

1. Prime Numbers

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

Check if a Number Is Prime

bool IsPrime(int n)
{
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}

Time Complexity

• O(vn)

2. Sieve of Eratosthenes

Used to generate all prime numbers up to N efficiently.

How It Works

1. Assume all numbers are prime

2. Remove multiples of 2

3. Remove multiples of 3

4. Continue until vn

C# Implementation

bool[] Sieve(int n)
{
    bool[] prime = Enumerable.Repeat(true, n + 1).ToArray();
    prime[0] = prime[1] = false;

    for (int i = 2; i * i <= n; i++)
    {
        if (prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }
    return prime;
}

Time Complexity

• O(n log log n)

3. Greatest Common Divisor (GCD) – Euclid’s Algorithm

GCD of two numbers is the largest number that divides both.

Euclid's Algorithm

int GCD(int a, int b)
{
    if (b == 0) return a;
    return GCD(b, a % b);
}

Time Complexity

• O(log(min(a, b)))

4. Least Common Multiple (LCM)

Using GCD:

LCM(a, b) = (a × b) / GCD(a, b)

C# Code

int LCM(int a, int b)
{
    return (a / GCD(a, b)) * b;
}

5. Modular Arithmetic

Modular arithmetic keeps numbers within a specific range.

Properties

(a + b) % m
(a - b) % m
(a * b) % m

Used in:

• Cryptography

• Hashing

• Competitive programming

6. Fast Exponentiation (Binary Exponentiation)

Computes a^b in O(log b) time.

Code

long FastPower(long a, long b)
{
    long result = 1;
    while (b > 0)
    {
        if ((b & 1) == 1)
            result *= a;

        a *= a;
        b >>= 1;
    }
    return result;
}

7. Modular Exponentiation

Computes (a^b) % m efficiently.

Code

long ModPower(long a, long b, long mod)
{
    long result = 1;
    a %= mod;

    while (b > 0)
    {
        if ((b & 1) == 1)
            result = (result * a) % mod;

        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

8. Modular Inverse

The modular inverse of a under mod m is a number x such that:

(a × x) % m = 1

Works only when:

GCD(a, m) = 1

Using Fermat’s Little Theorem (m must be prime)

a^(m-2) % m

Code

long ModInverse(long a, long m)
{
    return ModPower(a, m - 2, m);
}

9. Factorization of Numbers

Simple Factorization

List<int> Factors(int n)
{
    List<int> list = new();
    for (int i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            list.Add(i);
            if (i != n / i) list.Add(n / i);
        }
    }
    return list;
}

10. Prime Factorization

List<int> PrimeFactors(int n)
{
    List<int> factors = new();

    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            factors.Add(i);
            n /= i;
        }
    }
    if (n > 1) factors.Add(n);

    return factors;
}

Applications of Mathematical Algorithms

1. Cryptography

RSA, Diffie-Hellman, hashing.

2. Competitive programming

Fast solutions for large constraints.

3. Computer graphics

Transformations and simulations.

4. Data compression

Prime-based hashing.

5. Machine learning

Optimization and modular arithmetic.

Summary

Mathematical algorithms form the backbone of many advanced computer science topics.

Key Takeaways

• Sieve efficiently generates primes

• GCD and LCM help solve number problems

• Fast exponentiation reduces power computation drastically

• Modular arithmetic is essential for cryptography

• Factorization helps in optimization and algebraic computations