Prime Factorization: Trial Division and Pollard's Rho

For each p from 2 to sqrt(n):
    while n divisible by p:
        add p to factors
        n //= p
if n > 1: n is a prime factor

#include <stdio.h>
#include <math.h>

void factorize(long long n) {
    printf("%lld = ", n);
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int exp = 0;
            while (n % p == 0) { exp++; n /= p; }
            printf("%lld^%d ", p, exp);
        }
    }
    if (n > 1) printf("%lld^1", n);
    printf("\n");
}

def factorize(n):
    factors = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
        p += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def count_divisors(n):
    factors = factorize(n)
    result = 1
    for exp in factors.values():
        result *= (exp + 1)
    return result

def sum_divisors(n):
    factors = factorize(n)
    result = 1
    for p, e in factors.items():
        result *= (p**(e+1) - 1) // (p - 1)
    return result

print(factorize(360))  # {2: 3, 3: 2, 5: 1} = 2^3 * 3^2 * 5
print(count_divisors(360))  # 24

#include <bits/stdc++.h>
using namespace std;

map<long long, int> factorize(long long n) {
    map<long long, int> factors;
    for (long long p = 2; p * p <= n; p++) {
        while (n % p == 0) {
            factors[p]++;
            n /= p;
        }
    }
    if (n > 1) factors[n]++;
    return factors;
}

// Count divisors using SPF sieve
vector<int> buildSPF(int n) {
    vector<int> spf(n + 1);
    iota(spf.begin(), spf.end(), 0);
    for (int p = 2; p * p <= n; p++) {
        if (spf[p] == p) {
            for (int m = p * p; m <= n; m += p)
                if (spf[m] == m) spf[m] = p;
        }
    }
    return spf;
}

map<int,int> fastFactorize(int n, vector<int>& spf) {
    map<int,int> factors;
    while (n > 1) {
        factors[spf[n]]++;
        n /= spf[n];
    }
    return factors;
}

import java.util.*;

public class PrimeFactors {
    public static Map<Long, Integer> factorize(long n) {
        Map<Long, Integer> factors = new LinkedHashMap<>();
        for (long p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                factors.merge(p, 1, Integer::sum);
                n /= p;
            }
        }
        if (n > 1) factors.put(n, 1);
        return factors;
    }

    public static long countDivisors(long n) {
        long count = 1;
        for (Map.Entry<Long, Integer> e : factorize(n).entrySet())
            count *= (e.getValue() + 1);
        return count;
    }
}

function factorize(n) {
    const factors = new Map();
    for (let p = 2; p * p <= n; p++) {
        while (n % p === 0) {
            factors.set(p, (factors.get(p) || 0) + 1);
            n = Math.floor(n / p);
        }
    }
    if (n > 1) factors.set(n, (factors.get(n) || 0) + 1);
    return factors;
}