1. Greatest Common Divisor via Euclidean Method

The Euclidean algorithm efficiently determines the largest shared divisor between two integers by repeatedly applying the modulo operation.

// Time Complexity: O(log(min(a, b)))
int compute_gcd(int first, int second) {
    while (second != 0) {
        int remainder = first % second;
        first = second;
        second = remainder;
    }
    return first;
}

2. Primality Verification

To verify if an enteger is prime, iterate through potential factors only up to its square root. If any divisor is found, the number is composite.

// Time Complexity: O(sqrt(n))
bool verify_primality(unsigned int candidate) {
    if (candidate <= 1) return false;
    for (unsigned int divisor = 2; divisor * divisor <= candidate; ++divisor) {
        if (candidate % divisor == 0) return false;
    }
    return true;
}

3. Prime Factorization

Decomposing an integer into its prime components involves iterating through divisors and counting their occurrences. Each discovered prime factor is reduced until it no longer divides the target.

// Time Complexity: O(sqrt(n))
void extract_prime_factors(int target) {
    for (int p = 2; p * p <= target; ++p) {
        if (target % p == 0) {
            int exponent = 0;
            while (target % p == 0) {
                target /= p;
                ++exponent;
            }
            std::cout << p << " " << exponent << "\n";
        }
    }
    if (target > 1) {
        std::cout << target << " " << 1 << "\n";
    }
}

4. Sieve of Eratosthenes

A classical approach to generate all primes within a range by iteratively marking multiples of discovered primes as composite.

// Time Complexity: O(n log log n)
const int LIMIT = 100005;
bool is_composite[LIMIT] = {false};
std::vector<int> prime_cache;

void sieve_standard(int upper_bound) {
    for (int num = 2; num <= upper_bound; ++num) {
        if (!is_composite[num]) {
            prime_cache.push_back(num);
            for (int multiple = num * 2; multiple <= upper_bound; multiple += num) {
                is_composite[multiple] = true;
            }
        }
    }
}

5. Linear Sieve Algorithm

This optimized sieve guaranetes each composite number is marked exactly once, utilizing the smallest prime factor to maintain linear time complexity.

// Time Complexity: O(n)
const int MAX_VAL = 100005;
int smallest_prime[MAX_VAL] = {0};
std::vector<int> prime_list;

void sieve_linear(int boundary) {
    for (int current = 2; current <= boundary; ++current) {
        if (smallest_prime[current] == 0) {
            smallest_prime[current] = current;
            prime_list.push_back(current);
        }
        for (size_t idx = 0; idx < prime_list.size(); ++idx) {
            int p = prime_list[idx];
            if (p > smallest_prime[current] || (long long)current * p > boundary) break;
            smallest_prime[current * p] = p;
        }
    }
}

6. Calculating Divisor Counts and Sums

Given a canonical prime factorization $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$:

• The total number of divisors equals $\prod_{i=1}^k (e_i + 1)$.
• The sum of all divisors corresponds to $\prod_{i=1}^k \sum_{j=0}^{e_i} p_i^j$, which can also be computed using the geometric series formula.

7. Enumerating All Divisors

Collecting every factor of a number requires checking values up to the square root. For each valid divisor $i$, both $i$ and $n/i$ are recorded, then the collection is sorted.

// Time Complexity: O(sqrt(n) * log(sqrt(n))) due to sorting
std::vector<int> collect_divisors(int number) {
    std::vector<int> factors;
    for (int i = 1; i * i <= number; ++i) {
        if (number % i == 0) {
            factors.push_back(i);
            if (i != number / i) {
                factors.push_back(number / i);
            }
        }
    }
    std::sort(factors.begin(), factors.end());
    return factors;
}

8. Euler's Totient Function

The function $\phi(n)$ counts integers up to $n$ that are coprime to $n$. It is computed using the multiplicative property: $\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})$. The implementation iteratively applies this transformation for each distinct prime factor.

int calculate_totient(int value) {
    int result = value;
    for (int factor = 2; factor * factor <= value; ++factor) {
        if (value % factor == 0) {
            while (value % factor == 0) value /= factor;
            result -= result / factor;
        }
    }
    if (value > 1) {
        result -= result / value;
    }
    return result;
}