A dozen small number problems — digits, divisors, primes, GCD, powers — that every later topic quietly relies on. Each one has an obvious loop and a better idea; learning to see the better idea (√n, Euclid, the sieve, squaring) is the real lesson.

Problem	Naive	Better idea	Time
Sum of `1..n`	loop	`n(n+1)/2`	`O(1)`
Count digits	convert to string	repeat `n //= 10`	`O(d)`, `d` = digits
Palindrome number	string reverse	build the reversed number	`O(d)`
Factorial	—	loop or recursion	`O(n)`
Trailing zeros of `n!`	compute `n!`	count factors of 5	`O(log₅ n)`
GCD	try every candidate	Euclid: `gcd(b, a mod b)`	`O(log min(a,b))`
LCM	try every multiple	`a / gcd · b`	`O(log min(a,b))`
Is prime?	divide by `2..n−1`	divide by `6k ± 1` up to `√n`	`O(√n)`
Prime factors	test every `i` for primality	divide out `2`, `3`, then `6k ± 1` up to `√n`	`O(√n)`
All divisors	test `1..n`	pairs `(i, n/i)` up to `√n`	`O(√n)`
All primes `≤ n`	test each number	Sieve of Eratosthenes	`O(n log log n)`
`xⁿ`	multiply `n` times	square-and-multiply	`O(log n)`

Sum of the first n natural numbers

The loop is the obvious O(n) solution; the formula is O(1). One subtlety: n(n + 1) may overflow before the division, so divide the even factor first — one of n and n + 1 is always even, which keeps every intermediate value within the final answer's size.

Python

def sum_loop(n):                      # O(n): add the numbers one by one
    total = 0
    for x in range(1, n + 1):
        total += x
    return total

def sum_formula(n):                   # O(1): divide the even factor first (no overflow)
    if n % 2 == 0:
        return (n // 2) * (n + 1)
    return ((n + 1) // 2) * n         # n odd → n + 1 is even

for n in (5, 50, 51):
    print(f"sum({n}): loop = {sum_loop(n)}, formula = {sum_formula(n)}")

C++

#include <iostream>
using namespace std;

long long sumLoop(int n) {            // O(n): add the numbers one by one
    long long total = 0;
    for (int x = 1; x <= n; x++) total += x;
    return total;
}

long long sumFormula(long long n) {   // O(1): divide the even factor first (no overflow)
    if (n % 2 == 0) return (n / 2) * (n + 1);
    return ((n + 1) / 2) * n;         // n odd → n + 1 is even
}

int main() {
    for (int n : {5, 50, 51})
        cout << "sum(" << n << "): loop = " << sumLoop(n) << ", formula = " << sumFormula(n) << "\n";
}

Java

public class Main {
    static long sumLoop(int n) {          // O(n): add the numbers one by one
        long total = 0;
        for (int x = 1; x <= n; x++) total += x;
        return total;
    }

    static long sumFormula(long n) {      // O(1): divide the even factor first (no overflow)
        if (n % 2 == 0) return (n / 2) * (n + 1);
        return ((n + 1) / 2) * n;         // n odd → n + 1 is even
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 50, 51})
            System.out.println("sum(" + n + "): loop = " + sumLoop(n) + ", formula = " + sumFormula(n));
    }
}

JavaScript

function sumLoop(n) {                 // O(n): add the numbers one by one
    let total = 0;
    for (let x = 1; x <= n; x++) total += x;
    return total;
}

function sumFormula(n) {              // O(1): divide the even factor first (no overflow)
    if (n % 2 === 0) return (n / 2) * (n + 1);
    return ((n + 1) / 2) * n;         // n odd → n + 1 is even
}

for (const n of [5, 50, 51])
    console.log(`sum(${n}): loop = ${sumLoop(n)}, formula = ${sumFormula(n)}`);

Output

sum(5): loop = 15, formula = 15
sum(50): loop = 1275, formula = 1275
sum(51): loop = 1326, formula = 1326

Time O(1) with the formula, O(n) with the loop · Space O(1)

Count digits

Python

def count_digits(n):
    n = abs(n)
    if n == 0:
        return 1                 # 0 is one digit, but the loop below would say 0
    count = 0
    while n > 0:
        n //= 10                 # drop the last digit
        count += 1
    return count

for n in (256, 75, 5, 0, 9253):
    print(n, "→", count_digits(n))

C++

#include <iostream>
#include <cstdlib>
using namespace std;

int countDigits(int n) {
    n = abs(n);
    if (n == 0) return 1;        // 0 is one digit, but the loop below would say 0
    int count = 0;
    while (n > 0) {
        n /= 10;                 // drop the last digit
        count++;
    }
    return count;
}

int main() {
    for (int n : {256, 75, 5, 0, 9253})
        cout << n << " → " << countDigits(n) << "\n";
}

Java

public class Main {
    static int countDigits(int n) {
        n = Math.abs(n);
        if (n == 0) return 1;        // 0 is one digit, but the loop below would say 0
        int count = 0;
        while (n > 0) {
            n /= 10;                 // drop the last digit
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        for (int n : new int[]{256, 75, 5, 0, 9253})
            System.out.println(n + " → " + countDigits(n));
    }
}

JavaScript

function countDigits(n) {
    n = Math.abs(n);
    if (n === 0) return 1;       // 0 is one digit, but the loop below would say 0
    let count = 0;
    while (n > 0) {
        n = Math.floor(n / 10);  // drop the last digit (no integer division in JS)
        count++;
    }
    return count;
}

for (const n of [256, 75, 5, 0, 9253])
    console.log(n, "→", countDigits(n));

Output

Time O(d) = O(log₁₀ n) · Space O(1)

Palindrome number

Reversing 12321 digit by digit

n = 12321, rev = 0
step 1: digit 1 → rev = 1        n = 1232
step 2: digit 2 → rev = 12       n = 123
step 3: digit 3 → rev = 123      n = 12
step 4: digit 2 → rev = 1232     n = 1
step 5: digit 1 → rev = 12321    n = 0   → rev == original → palindrome

Python

def is_palindrome(n):
    if n < 0:
        return False             # "-121" reversed is "121-"
    rev, x = 0, n
    while x > 0:
        rev = rev * 10 + x % 10  # append the last digit of x to rev
        x //= 10
    return rev == n

for n in (12321, 42322, 78987, 10):
    print(n, "→", "Yes" if is_palindrome(n) else "No")

C++

#include <iostream>
using namespace std;

bool isPalindrome(long long n) {
    if (n < 0) return false;     // "-121" reversed is "121-"
    long long rev = 0, x = n;
    while (x > 0) {
        rev = rev * 10 + x % 10; // append the last digit of x to rev
        x /= 10;
    }
    return rev == n;
}

int main() {
    for (long long n : {12321, 42322, 78987, 10})
        cout << n << " → " << (isPalindrome(n) ? "Yes" : "No") << "\n";
}

Java

public class Main {
    static boolean isPalindrome(long n) {
        if (n < 0) return false;     // "-121" reversed is "121-"
        long rev = 0, x = n;
        while (x > 0) {
            rev = rev * 10 + x % 10; // append the last digit of x to rev
            x /= 10;
        }
        return rev == n;
    }

    public static void main(String[] args) {
        for (long n : new long[]{12321, 42322, 78987, 10})
            System.out.println(n + " → " + (isPalindrome(n) ? "Yes" : "No"));
    }
}

JavaScript

function isPalindrome(n) {
    if (n < 0) return false;             // "-121" reversed is "121-"
    let rev = 0, x = n;
    while (x > 0) {
        rev = rev * 10 + (x % 10);       // append the last digit of x to rev
        x = Math.floor(x / 10);
    }
    return rev === n;
}

for (const n of [12321, 42322, 78987, 10])
    console.log(n, "→", isPalindrome(n) ? "Yes" : "No");

Output

12321 → Yes
42322 → No
78987 → Yes
10 → No

Time O(d) · Space O(1)

Factorial

Python

def fact_iterative(n):           # O(n) time, O(1) auxiliary space
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def fact_recursive(n):           # O(n) time, O(n) stack frames
    if n == 0:                   # base case: 0! = 1 (not n == 1, or fact(0) never stops)
        return 1
    return n * fact_recursive(n - 1)

for n in (0, 3, 5, 10, 20):
    print(f"{n}! = {fact_iterative(n)} (iterative) {fact_recursive(n)} (recursive)")

C++

#include <iostream>
using namespace std;

long long factIterative(int n) {     // O(n) time, O(1) auxiliary space
    long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

long long factRecursive(int n) {     // O(n) time, O(n) stack frames
    if (n == 0) return 1;            // base case: 0! = 1
    return n * factRecursive(n - 1);
}

int main() {
    for (int n : {0, 3, 5, 10, 20})
        cout << n << "! = " << factIterative(n) << " (iterative) " << factRecursive(n) << " (recursive)\n";
}

Java

public class Main {
    static long factIterative(int n) {   // O(n) time, O(1) auxiliary space
        long result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }

    static long factRecursive(int n) {   // O(n) time, O(n) stack frames
        if (n == 0) return 1;            // base case: 0! = 1
        return n * factRecursive(n - 1);
    }

    public static void main(String[] args) {
        for (int n : new int[]{0, 3, 5, 10, 20})
            System.out.println(n + "! = " + factIterative(n) + " (iterative) " + factRecursive(n) + " (recursive)");
    }
}

JavaScript

function factIterative(n) {          // O(n) time, O(1) auxiliary space — BigInt: 20! > 2^53
    let result = 1n;
    for (let i = 2n; i <= BigInt(n); i++) result *= i;
    return result;
}

function factRecursive(n) {          // O(n) time, O(n) stack frames
    if (n === 0) return 1n;          // base case: 0! = 1
    return BigInt(n) * factRecursive(n - 1);
}

for (const n of [0, 3, 5, 10, 20])
    console.log(`${n}! = ${factIterative(n)} (iterative) ${factRecursive(n)} (recursive)`);

Output

0! = 1 (iterative) 1 (recursive)
3! = 6 (iterative) 6 (recursive)
5! = 120 (iterative) 120 (recursive)
10! = 3628800 (iterative) 3628800 (recursive)
20! = 2432902008176640000 (iterative) 2432902008176640000 (recursive)

Time O(n) · Space O(1) iterative, O(n) recursive (call stack)

Trailing zeros in a factorial

zeros(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … (until the term is 0)

Python

def trailing_zeros(n):
    count = 0
    power = 5
    while n // power >= 1:       # 5, 25, 125, … each adds one more factor of 5
        count += n // power
        power *= 5
    return count

for n in (5, 10, 25, 50, 100):
    print(n, "→", trailing_zeros(n))

C++

#include <iostream>
using namespace std;

int trailingZeros(int n) {
    int count = 0;
    for (long long power = 5; n / power >= 1; power *= 5)   // 5, 25, 125, …
        count += n / power;
    return count;
}

int main() {
    for (int n : {5, 10, 25, 50, 100})
        cout << n << " → " << trailingZeros(n) << "\n";
}

Java

public class Main {
    static int trailingZeros(int n) {
        int count = 0;
        for (long power = 5; n / power >= 1; power *= 5)     // 5, 25, 125, …
            count += n / power;
        return count;
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 10, 25, 50, 100})
            System.out.println(n + " → " + trailingZeros(n));
    }
}

JavaScript

function trailingZeros(n) {
    let count = 0;
    for (let power = 5; Math.floor(n / power) >= 1; power *= 5)   // 5, 25, 125, …
        count += Math.floor(n / power);
    return count;
}

for (const n of [5, 10, 25, 50, 100])
    console.log(n, "→", trailingZeros(n));

Output

Time O(log₅ n) · Space O(1)

GCD / HCF of two numbers

The greatest common divisor (also called highest common factor) is the largest number that divides both. Factors of 20: 1 2 4 5 10 20; factors of 28: 1 2 4 7 14 28; the largest shared one is 4.

The naive method walks down from min(a, b) until it finds a common divisor — O(min(a, b)):

Python

def gcd_naive(a, b):
    result = min(a, b)
    while result > 0:
        if a % result == 0 and b % result == 0:
            break                       # first common divisor from the top is the greatest
        result -= 1
    return result

print(gcd_naive(20, 28))    # 4
print(gcd_naive(100, 75))   # 25

Euclid's algorithm: the remainder shrinks fast

gcd(1071, 462)
  1071 = 2 · 462 + 147   →  gcd(462, 147)
   462 = 3 · 147 +  21   →  gcd(147, 21)
   147 = 7 ·  21 +   0   →  gcd(21, 0) = 21

Python

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)   # gcd(a, b) = gcd(b, a mod b)

def gcd(a, b):                       # same idea, iterative: O(1) space
    while b:
        a, b = b, a % b
    return a

for a, b in [(20, 28), (100, 75), (17, 5), (1071, 462), (0, 9)]:
    assert gcd(a, b) == gcd_recursive(a, b)
    print(f"gcd({a}, {b}) = {gcd(a, b)}")

C++

#include <iostream>
using namespace std;

int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);   // gcd(a, b) = gcd(b, a mod b)
}

int gcd(int a, int b) {              // same idea, iterative: O(1) space
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int pairs[5][2] = {{20, 28}, {100, 75}, {17, 5}, {1071, 462}, {0, 9}};
    for (auto& ab : pairs) {
        int g = gcd(ab[0], ab[1]);
        if (g != gcdRecursive(ab[0], ab[1])) return 1;
        cout << "gcd(" << ab[0] << ", " << ab[1] << ") = " << g << "\n";
    }
}

Java

public class Main {
    static int gcdRecursive(int a, int b) {
        if (b == 0) return a;
        return gcdRecursive(b, a % b);   // gcd(a, b) = gcd(b, a mod b)
    }

    static int gcd(int a, int b) {       // same idea, iterative: O(1) space
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    public static void main(String[] args) {
        int[][] pairs = {{20, 28}, {100, 75}, {17, 5}, {1071, 462}, {0, 9}};
        for (int[] ab : pairs) {
            int g = gcd(ab[0], ab[1]);
            assert g == gcdRecursive(ab[0], ab[1]);
            System.out.println("gcd(" + ab[0] + ", " + ab[1] + ") = " + g);
        }
    }
}

JavaScript

function gcdRecursive(a, b) {
    if (b === 0) return a;
    return gcdRecursive(b, a % b);   // gcd(a, b) = gcd(b, a mod b)
}

function gcd(a, b) {                 // same idea, iterative: O(1) space
    while (b !== 0) [a, b] = [b, a % b];
    return a;
}

for (const [a, b] of [[20, 28], [100, 75], [17, 5], [1071, 462], [0, 9]]) {
    const g = gcd(a, b);
    if (g !== gcdRecursive(a, b)) throw new Error("mismatch");
    console.log(`gcd(${a}, ${b}) = ${g}`);
}

Output

gcd(20, 28) = 4
gcd(100, 75) = 25
gcd(17, 5) = 1
gcd(1071, 462) = 21
gcd(0, 9) = 9

Time O(log min(a, b)) · Space O(1) iterative, O(log min(a, b)) recursive

The original notes also had a subtraction-only version, while a != b: subtract the smaller from the larger. It is correct, but it is not the optimised one: for gcd(1, 10⁹) it loops a billion times, whereas the modulo version finishes in one step. Keep it as a curiosity:

Python

def gcd_subtract(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a                   # each step removes one multiple — O(max(a, b)) worst case
    return a

print(gcd_subtract(20, 28))    # 4

LCM of two numbers

The least common multiple is the smallest positive number divisible by both. The naive way starts at max(a, b) and counts up until a common multiple appears — up to a · b steps:

Python

def lcm_naive(a, b):
    res = max(a, b)
    while True:
        if res % a == 0 and res % b == 0:
            return res
        res += 1

print(lcm_naive(15, 20))   # 60

Python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b        # divide first: a/g is an integer, product stays small

for a, b in [(15, 20), (4, 6), (7, 13), (12, 18)]:
    print(f"lcm({a}, {b}) = {lcm(a, b)}")

C++

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) { long long r = a % b; a = b; b = r; }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;        // divide first: a/g is an integer, product stays small
}

int main() {
    long long pairs[4][2] = {{15, 20}, {4, 6}, {7, 13}, {12, 18}};
    for (auto& ab : pairs)
        cout << "lcm(" << ab[0] << ", " << ab[1] << ") = " << lcm(ab[0], ab[1]) << "\n";
}

Java

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) { long r = a % b; a = b; b = r; }
        return a;
    }

    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;        // divide first: a/g is an integer, product stays small
    }

    public static void main(String[] args) {
        long[][] pairs = {{15, 20}, {4, 6}, {7, 13}, {12, 18}};
        for (long[] ab : pairs)
            System.out.println("lcm(" + ab[0] + ", " + ab[1] + ") = " + lcm(ab[0], ab[1]));
    }
}

JavaScript

function gcd(a, b) {
    while (b !== 0) [a, b] = [b, a % b];
    return a;
}

function lcm(a, b) {
    return (a / gcd(a, b)) * b;      // divide first: a/g is an integer, product stays small
}

for (const [a, b] of [[15, 20], [4, 6], [7, 13], [12, 18]])
    console.log(`lcm(${a}, ${b}) = ${lcm(a, b)}`);

Output

lcm(15, 20) = 60
lcm(4, 6) = 12
lcm(7, 13) = 91
lcm(12, 18) = 36

Time O(log min(a, b)) · Space O(1)

Check for prime

A prime has exactly two divisors, 1 and itself; 1 is not prime. The naive test tries every i from 2 to n − 1 — O(n):

Python

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

print(is_prime_naive(11))   # True
print(is_prime_naive(10))   # False

Handle the small cases
n ≤ 1 → not prime; n ≤ 3 → prime.
Remove multiples of 2 and 3
If n % 2 == 0 or n % 3 == 0 → not prime.
Test 6k ± 1 up to √n
i = 5, 11, 17… (step 6), checking both i and i + 2. Use i * i <= n instead of sqrt to avoid floating point.

Python

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:                # only up to √n
        if n % i == 0 or n % (i + 2) == 0:   # 6k - 1 and 6k + 1
            return False
        i += 6
    return True

for n in (1, 2, 10, 11, 97, 1000003, 1000001):
    print(n, "→", "Yes" if is_prime(n) else "No")

C++

#include <iostream>
using namespace std;

bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6)          // only up to √n
        if (n % i == 0 || n % (i + 2) == 0) return false;   // 6k - 1 and 6k + 1
    return true;
}

int main() {
    for (long long n : {1, 2, 10, 11, 97, 1000003, 1000001})
        cout << n << " → " << (isPrime(n) ? "Yes" : "No") << "\n";
}

Java

public class Main {
    static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long i = 5; i * i <= n; i += 6)              // only up to √n
            if (n % i == 0 || n % (i + 2) == 0) return false;   // 6k - 1 and 6k + 1
        return true;
    }

    public static void main(String[] args) {
        for (long n : new long[]{1, 2, 10, 11, 97, 1000003, 1000001})
            System.out.println(n + " → " + (isPrime(n) ? "Yes" : "No"));
    }
}

JavaScript

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5; i * i <= n; i += 6)                  // only up to √n
        if (n % i === 0 || n % (i + 2) === 0) return false;   // 6k - 1 and 6k + 1
    return true;
}

for (const n of [1, 2, 10, 11, 97, 1000003, 1000001])
    console.log(n, "→", isPrime(n) ? "Yes" : "No");

Output

1 → No
2 → Yes
10 → No
11 → Yes
97 → Yes
1000003 → Yes
1000001 → No

Time O(√n) · Space O(1)

Prime factorization

The original notes tested every i from 2 to n for primality and then divided it out — O(n √n). That primality test is unnecessary: if you divide out each factor completely as soon as you meet it, every later i that divides n is automatically prime (all its smaller factors are already gone).

Python

def prime_factors(n):
    factors = []
    while n % 2 == 0:                 # all the 2s
        factors.append(2)
        n //= 2
    while n % 3 == 0:                 # all the 3s
        factors.append(3)
        n //= 3
    i = 5
    while i * i <= n:                 # 6k ± 1 candidates up to √n
        for d in (i, i + 2):
            while n % d == 0:
                factors.append(d)
                n //= d
        i += 6
    if n > 1:                         # one prime factor > √n may remain
        factors.append(n)
    return factors

for n in (100, 315, 97, 1001, 1):
    print(n, "→", *prime_factors(n))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> primeFactors(int n) {
    vector<int> factors;
    while (n % 2 == 0) { factors.push_back(2); n /= 2; }   // all the 2s
    while (n % 3 == 0) { factors.push_back(3); n /= 3; }   // all the 3s
    for (int i = 5; i * i <= n; i += 6)                    // 6k ± 1 candidates up to √n
        for (int d : {i, i + 2})
            while (n % d == 0) { factors.push_back(d); n /= d; }
    if (n > 1) factors.push_back(n);                       // one prime factor > √n may remain
    return factors;
}

int main() {
    for (int n : {100, 315, 97, 1001, 1}) {
        cout << n << " →";
        for (int f : primeFactors(n)) cout << " " << f;
        cout << "\n";
    }
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        while (n % 2 == 0) { factors.add(2); n /= 2; }        // all the 2s
        while (n % 3 == 0) { factors.add(3); n /= 3; }        // all the 3s
        for (int i = 5; i * i <= n; i += 6)                   // 6k ± 1 candidates up to √n
            for (int d : new int[]{i, i + 2})
                while (n % d == 0) { factors.add(d); n /= d; }
        if (n > 1) factors.add(n);                            // one prime factor > √n may remain
        return factors;
    }

    public static void main(String[] args) {
        for (int n : new int[]{100, 315, 97, 1001, 1}) {
            StringBuilder sb = new StringBuilder(n + " →");
            for (int f : primeFactors(n)) sb.append(' ').append(f);
            System.out.println(sb);
        }
    }
}

JavaScript

function primeFactors(n) {
    const factors = [];
    while (n % 2 === 0) { factors.push(2); n /= 2; }         // all the 2s
    while (n % 3 === 0) { factors.push(3); n /= 3; }         // all the 3s
    for (let i = 5; i * i <= n; i += 6)                      // 6k ± 1 candidates up to √n
        for (const d of [i, i + 2])
            while (n % d === 0) { factors.push(d); n /= d; }
    if (n > 1) factors.push(n);                              // one prime factor > √n may remain
    return factors;
}

for (const n of [100, 315, 97, 1001, 1])
    console.log(`${n} →${primeFactors(n).map(f => " " + f).join("")}`);

Output

100 → 2 2 5 5
315 → 3 3 5 7
97 → 97
1001 → 7 11 13
1 →

Time O(√n) · Space O(log n) for the list of factors

All divisors of a number

Naively, test every i in 1..n — O(n):

Python

def divisors_naive(n):
    return [i for i in range(1, n + 1) if n % i == 0]

print(divisors_naive(10))   # [1, 2, 5, 10]

Emitting both members as you go gives the divisors unsorted (1 100 2 50 4 25 5 20 10). To get them sorted with no extra memory, print the small members on the way up and the large partners on the way back down:

Python

import math

def divisors_unsorted(n):            # O(√n), pairs printed together
    out = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            out.append(i)
            if n // i != i:          # perfect square: don't print √n twice
                out.append(n // i)
        i += 1
    return out

print(divisors_unsorted(100))        # [1, 100, 2, 50, 4, 25, 5, 20, 10]

Python

def divisors_sorted(n):
    out = []
    i = 1
    while i * i < n:                   # ascending: small members of each pair
        if n % i == 0:
            out.append(i)
        i += 1
    if i * i == n:                     # perfect square: √n once
        out.append(i)
    i -= 1 if i * i == n else 0
    while i >= 1:                      # descending i → ascending partners n / i
        if n % i == 0 and i * i != n:
            out.append(n // i)
        i -= 1
    return out

for n in (10, 100, 36, 97):
    print(n, "→", *divisors_sorted(n))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> divisorsSorted(int n) {
    vector<int> out;
    int i = 1;
    for (; i * i < n; i++)                      // ascending: small members of each pair
        if (n % i == 0) out.push_back(i);
    if (i * i == n) out.push_back(i);           // perfect square: √n once
    for (i = i * i == n ? i - 1 : i; i >= 1; i--)   // descending i → ascending partners n / i
        if (n % i == 0 && i * i != n) out.push_back(n / i);
    return out;
}

int main() {
    for (int n : {10, 100, 36, 97}) {
        cout << n << " →";
        for (int d : divisorsSorted(n)) cout << " " << d;
        cout << "\n";
    }
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> divisorsSorted(int n) {
        List<Integer> out = new ArrayList<>();
        int i = 1;
        for (; i * i < n; i++)                      // ascending: small members of each pair
            if (n % i == 0) out.add(i);
        if (i * i == n) out.add(i);                 // perfect square: √n once
        for (i = i * i == n ? i - 1 : i; i >= 1; i--)   // descending i → ascending partners n / i
            if (n % i == 0 && i * i != n) out.add(n / i);
        return out;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 100, 36, 97}) {
            StringBuilder sb = new StringBuilder(n + " →");
            for (int d : divisorsSorted(n)) sb.append(' ').append(d);
            System.out.println(sb);
        }
    }
}

JavaScript

function divisorsSorted(n) {
    const out = [];
    let i = 1;
    for (; i * i < n; i++)                          // ascending: small members of each pair
        if (n % i === 0) out.push(i);
    if (i * i === n) out.push(i);                   // perfect square: √n once
    for (i = i * i === n ? i - 1 : i; i >= 1; i--)  // descending i → ascending partners n / i
        if (n % i === 0 && i * i !== n) out.push(n / i);
    return out;
}

for (const n of [10, 100, 36, 97])
    console.log(`${n} →${divisorsSorted(n).map(d => " " + d).join("")}`);

Output

10 → 1 2 5 10
100 → 1 2 4 5 10 20 25 50 100
36 → 1 2 3 4 6 9 12 18 36
97 → 1 97

Time O(√n) · Space O(1) besides the output

Sieve of Eratosthenes

To list all primes up to n, testing each number separately costs O(n √n). The sieve does far better by working the other way round: instead of asking “is x prime?”, it crosses out every multiple of each prime found.

Crossing out multiples: everything still standing is prime

n = 30, after sieving with 2, 3 and 5 (5² = 25 ≤ 30, 7² = 49 > 30 → stop)

 2  3  x  5  x  7  x  x  x 11  x 13  x  x  x 17  x 19  x  x  x 23  x  x  x  x  x 29  x
 ^  ^     ^     ^           ^     ^           ^     ^           ^                 ^
primes: 2 3 5 7 11 13 17 19 23 29

Python

def sieve(n):
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:                          # only up to √n
        if is_prime[i]:
            for j in range(i * i, n + 1, i):   # start at i²: smaller multiples are done
                is_prime[j] = False
        i += 1
    return [x for x in range(2, n + 1) if is_prime[x]]

print("primes ≤ 10:", *sieve(10))
print("primes ≤ 50:", *sieve(50))
print("count ≤ 1000:", len(sieve(1000)))

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> sieve(int n) {
    vector<int> primes;
    if (n < 2) return primes;
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++)                     // only up to √n
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)          // start at i²: smaller multiples are done
                isPrime[j] = false;
    for (int x = 2; x <= n; x++)
        if (isPrime[x]) primes.push_back(x);
    return primes;
}

int main() {
    for (int n : {10, 50}) {
        cout << "primes ≤ " << n << ":";
        for (int p : sieve(n)) cout << " " << p;
        cout << "\n";
    }
    cout << "count ≤ 1000: " << sieve(1000).size() << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> sieve(int n) {
        List<Integer> primes = new ArrayList<>();
        if (n < 2) return primes;
        boolean[] composite = new boolean[n + 1];        // false = still prime
        for (int i = 2; (long) i * i <= n; i++)          // only up to √n
            if (!composite[i])
                for (int j = i * i; j <= n; j += i)      // start at i²: smaller multiples are done
                    composite[j] = true;
        for (int x = 2; x <= n; x++)
            if (!composite[x]) primes.add(x);
        return primes;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 50}) {
            StringBuilder sb = new StringBuilder("primes ≤ " + n + ":");
            for (int p : sieve(n)) sb.append(' ').append(p);
            System.out.println(sb);
        }
        System.out.println("count ≤ 1000: " + sieve(1000).size());
    }
}

JavaScript

function sieve(n) {
    if (n < 2) return [];
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i <= n; i++)                     // only up to √n
        if (isPrime[i])
            for (let j = i * i; j <= n; j += i)          // start at i²: smaller multiples are done
                isPrime[j] = false;
    const primes = [];
    for (let x = 2; x <= n; x++) if (isPrime[x]) primes.push(x);
    return primes;
}

for (const n of [10, 50]) console.log(`primes ≤ ${n}: ${sieve(n).join(" ")}`);
console.log("count ≤ 1000:", sieve(1000).length);

Output

primes ≤ 10: 2 3 5 7
primes ≤ 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
count ≤ 1000: 168

Time O(n log log n) · Space O(n)

Computing power xⁿ

Multiplying x by itself n times is O(n):

Python

def power_naive(x, n):
    result = 1
    for _ in range(n):
        result *= x
    return result

print(power_naive(2, 3))    # 8
print(power_naive(3, 5))    # 243

Recursive power: n halves at every level

3^13 = 3 · (3^6)²            13 is odd
3^6  =     (3^3)²             6 is even
3^3  = 3 · (3^1)²             3 is odd
3^1  = 3 · (3^0)²
3^0  = 1                      base case  →  4 levels for n = 13

Python

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)        # compute x^(n/2) once …
    if n % 2 == 0:
        return half * half         # … and square it
    return x * half * half

for x, n in [(2, 3), (3, 5), (3, 13), (2, 30), (5, 0)]:
    print(f"{x}^{n} = {power(x, n)}")

C++

#include <iostream>
using namespace std;

long long power(long long x, int n) {
    if (n == 0) return 1;
    long long half = power(x, n / 2);   // compute x^(n/2) once …
    if (n % 2 == 0) return half * half; // … and square it
    return x * half * half;
}

int main() {
    int cases[5][2] = {{2, 3}, {3, 5}, {3, 13}, {2, 30}, {5, 0}};
    for (auto& c : cases)
        cout << c[0] << "^" << c[1] << " = " << power(c[0], c[1]) << "\n";
}

Java

public class Main {
    static long power(long x, int n) {
        if (n == 0) return 1;
        long half = power(x, n / 2);        // compute x^(n/2) once …
        if (n % 2 == 0) return half * half; // … and square it
        return x * half * half;
    }

    public static void main(String[] args) {
        int[][] cases = {{2, 3}, {3, 5}, {3, 13}, {2, 30}, {5, 0}};
        for (int[] c : cases)
            System.out.println(c[0] + "^" + c[1] + " = " + power(c[0], c[1]));
    }
}

JavaScript

function power(x, n) {
    if (n === 0) return 1;
    const half = power(x, Math.floor(n / 2));   // compute x^(n/2) once …
    if (n % 2 === 0) return half * half;        // … and square it
    return x * half * half;
}

for (const [x, n] of [[2, 3], [3, 5], [3, 13], [2, 30], [5, 0]])
    console.log(`${x}^${n} = ${power(x, n)}`);

Output

2^3 = 8
3^5 = 243
3^13 = 1594323
2^30 = 1073741824
5^0 = 1

Time O(log n) · Space O(log n) call stack

Iterative power: binary exponentiation

The square-and-multiply loop on 3^5

3^5, n = 5 = 101₂          res = 1,  x = 3
bit 0 = 1 → res = 1 · 3 = 3        x = 3² = 9        n = 2 (10₂)
bit 1 = 0 → res unchanged          x = 9² = 81       n = 1 (1₂)
bit 2 = 1 → res = 3 · 81 = 243     x = 81² = 6561    n = 0 → stop

The real-world form adds a modulus: x^n mod m for huge n (RSA, hashing, combinatorics mod 10⁹ + 7). Reduce after every multiplication so the numbers never exceed m².

Python

def power(x, n):
    res = 1
    while n > 0:
        if n & 1:                 # current bit is 1: multiply this power of x in
            res *= x
        x *= x                    # x, x², x⁴, x⁸ …
        n >>= 1                   # next bit
    return res

def power_mod(x, n, m):
    res, x = 1, x % m
    while n > 0:
        if n & 1:
            res = res * x % m     # reduce after every multiplication
        x = x * x % m
        n >>= 1
    return res

for x, n in [(3, 5), (2, 30), (7, 0)]:
    print(f"{x}^{n} = {power(x, n)}")
M = 1_000_000_007
print(f"2^100 mod {M} = {power_mod(2, 100, M)}")
print(f"3^200 mod {M} = {power_mod(3, 200, M)}")

C++

#include <iostream>
using namespace std;

long long power(long long x, int n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res *= x;      // current bit is 1: multiply this power of x in
        x *= x;                   // x, x², x⁴, x⁸ …
        n >>= 1;                  // next bit
    }
    return res;
}

long long powerMod(long long x, long long n, long long m) {
    long long res = 1;
    x %= m;
    while (n > 0) {
        if (n & 1) res = res * x % m;   // reduce after every multiplication
        x = x * x % m;
        n >>= 1;
    }
    return res;
}

int main() {
    int cases[3][2] = {{3, 5}, {2, 30}, {7, 0}};
    for (auto& c : cases) cout << c[0] << "^" << c[1] << " = " << power(c[0], c[1]) << "\n";
    const long long M = 1000000007LL;
    cout << "2^100 mod " << M << " = " << powerMod(2, 100, M) << "\n";
    cout << "3^200 mod " << M << " = " << powerMod(3, 200, M) << "\n";
}

Java

public class Main {
    static long power(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) res *= x;   // current bit is 1: multiply this power of x in
            x *= x;                       // x, x², x⁴, x⁸ …
            n >>= 1;                      // next bit
        }
        return res;
    }

    static long powerMod(long x, long n, long m) {
        long res = 1;
        x %= m;
        while (n > 0) {
            if ((n & 1) == 1) res = res * x % m;   // reduce after every multiplication
            x = x * x % m;
            n >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] cases = {{3, 5}, {2, 30}, {7, 0}};
        for (int[] c : cases) System.out.println(c[0] + "^" + c[1] + " = " + power(c[0], c[1]));
        final long M = 1_000_000_007L;
        System.out.println("2^100 mod " + M + " = " + powerMod(2, 100, M));
        System.out.println("3^200 mod " + M + " = " + powerMod(3, 200, M));
    }
}

JavaScript

function power(x, n) {
    let res = 1;
    while (n > 0) {
        if (n & 1) res *= x;      // current bit is 1: multiply this power of x in
        x *= x;                   // x, x², x⁴, x⁸ …
        n >>= 1;                  // next bit
    }
    return res;
}

function powerMod(x, n, m) {      // BigInt: res * x can exceed 2^53
    let res = 1n;
    x = BigInt(x) % m;
    while (n > 0) {
        if (n & 1) res = res * x % m;   // reduce after every multiplication
        x = x * x % m;
        n >>= 1;
    }
    return res;
}

for (const [x, n] of [[3, 5], [2, 30], [7, 0]]) console.log(`${x}^${n} = ${power(x, n)}`);
const M = 1000000007n;
console.log(`2^100 mod ${M} = ${powerMod(2, 100, M)}`);
console.log(`3^200 mod ${M} = ${powerMod(3, 200, M)}`);

Output

3^5 = 243
2^30 = 1073741824
7^0 = 1
2^100 mod 1000000007 = 976371285
3^200 mod 1000000007 = 136318165

Time O(log n) · Space O(1)

Interview Q&A

Why does checking divisors up to √n suffice for a primality test?

Explain Euclid's algorithm and its complexity.

How do you compute the LCM without overflow?

How many trailing zeros does 100! have, and why not count factors of 2?

Why does the sieve start crossing out at i² and stop at √n?

How does fast exponentiation reach O(log n), and where is it used?