Prime Number

Prime Factorization

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

Algorithm in $O(\sqrt{n})$

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;
}

• Actually proving this works and the time complexity is a bit trickier
• The while loop essentially reduces the number down and eliminates the possibility that $d|n$ for the new $n$.
  • Total number of divisions for the number $n$ is $O(\log n)$, so the bigger term is the $\sqrt{n}$

Intuition: You get rid of all the divisors of $n$ for that particular given prime.

Why do we only need to go up to \sqrt n for the divisors?

Because there can be at most 1 prime factor greater than $\sqrt{n}$.

• Proof: Assume by contradiction that $n$ has two or more prime factors greater than $\sqrt{n}$. Let us denote thee two prime factors of $n$ as $a$ and $b$, so $a|n$ and $b|n$. Also $a\cdot b|n$ (since $a$ and $b$ are prime factors). However notice that $a,b>\sqrt{n}$, so $a\cdot b>n$, so $a\cdot b\nmid n$. This is a contradiction.

Because of this result, we only check for factors up to $\sqrt{n}$. Then, if $n$ is still greater than 1, then we can conclude that $n$ is prime itself (otherwise, we would have already found the other prime factors).

An even faster speedup!

Learned this through CP, towards the end of 2024.

If you precompute the primes, you can speedup by a factor of $1/log(n)$. See below! You don’t have to go through all numbers, including non-prime numbers.

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;
}

• Here, you don’t reduce down $n$

Problems

Speedup #1

I did this ~mid december 2024.

This was quite an interesting problem that I solved: https://codeforces.com/problemset/problem/1771/C

Passing the time limits was quite tricky. But essentially, it relied on your understanding of how trial division works.

• You need to do ${\sqrt{a}}_i$, but if you precompute the primes, you actually improve to $\sqrt{\frac{a_i}{\log a_i}}$

Excerpt from my solution:

...
for (int i = 0; i < n; i++) {
    for (int prime : primes) {
        if (prime * prime > a[i]) {
            break;
        }
 
        // do some processing
        factors.push_back(prime);
 
        while (a[i] % prime == 0) {
            a[i] /= prime;
        }
    }
    if (a[i] > 1) {
        factors.push_back(a[i]);
    }

I used this in another problem: https://codeforces.com/contest/1775/problem/D

• Figured out the prime factorization in $\sqrt{\frac{a_i}{\log (a_i)}}$

A little confused about the log

Like where does this log come from? I know from the Prime Number Theorem that the density of prime numbers up to $n$ is $\frac{n}{\ln n}$. We are supposed to visit all numbers up to $a_i$. We have our initial speed by only going up to $\sqrt{a_i}$. But we have an even better speedup where we only visit the prime numbers, and as long as those prime numbers are smaller then $\sqrt{(}{a}_i)$.

So how many is it?

• I’m not sure if its $\sqrt{\frac{a_i}{\log (a_i)}}$ or $\frac{{\sqrt{a}}_i}{\log (a_i)}$. The editorial uses the second notation.

Problem #2

https://codeforces.com/problemset/problem/1766/D Really proud how I was able to figure out the idea of distances and gcd.

I made the early observation about how the maximum length of the chain is $y-x$ . They say that $gcd(x+k,y+k)=gcd(x+k,y-x)$

And I made the observation that we can simply examine the prime numbers, and it’s one of those that must be the first time.

However, my get_primes implementation, even with the square root and precomputing the primes, was not fast enough.

We can actually have an array of size 1e7!! I don’t know that

This is the trick implementation, using the mind array that allowed me to pass.

mind → minD = min divisor

const int N = 1e7 + 5;
 
int mind[N];
 
void precalc() {
    for (int i = 0; i < N; i++) {
        mind[i] = i;
    }
 
    for (int p = 2; p < N; p++) {
        if (mind[p] != p) {
            continue;
        }
        for (int d = 2 * p; d < N; d += p) {
            mind[d] = min(mind[d], p);
        }
    }
}
 
vector<int> get_primes(int v) {
    vector<int> ps;
    while (v > 1) {
        if (ps.empty() || ps.back() != mind[v]) {
            ps.push_back(mind[v]);
        }
        v /= mind[v];
    }
    return ps;
}

• This implementation allows jumps, to get us our logN speed, as opposed to a sqrt factor!! You are guaranteed to jump at least twice each time. Actually pretty good algo!!

Related

• Sieve of Erastosthenes
• Divisibility of Integers