Prime Number

Prime Factorization

https://cp-algorithms.com/algebra/factorization.html

vector<long long> trial_division1(long long n) {
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

Factors of a Number

What about getting all the factors of a number?

• If you have $n$ prime factors, then you end up with $2^n$ factors, and you could exhaustively search it with all possible subsets , but this is a little tedious…also gives me TLE
• saw this on problem 1977C

Bruh you stupid.

A much easier way is the following, a number $n$ has a most $2\sqrt{n}$ factors.

• Because any number bigger than $\sqrt{n}$ that is a factor $n$ needs to be multiplied by a number smaller than $\sqrt{n}$, so you can just iterate over $\sqrt{n}$.

Factors of number

vector<int> divisors(int n) {
    vector<int> div;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            div.push_back(i);
            if (i != n / i) {
                div.push_back(n / i);
            }
        }
    }
    sort(div.begin(), div.end());
    return div;
}

Related

• Sieve of Erastosthenes
• Divisibility of Integers