Prime Factors Algorithm – A beginner’s Guide

Hello guys, welcome back to “code with asharam”. I will continue with my mathematics for competitive programming series in this post. In the last post, I discussed various Prime Numbers algorithms. One of the most important topics related to Prime Numbers is Prime Factors. You can find at least one problem related to prime factors in one out of every three contest. Hence, In this post, I will discuss some of the Prime Factors Algorithm which are frequently used in competitive programming. So, let’s gear up to take a dive deep and insightful oceans of Prime Factors algorithm.

A gentle introduction to prime factors

Prime numbers which divides a number are called its prime factors and the numbers which divides it are called its divisors. I have told you in prime numbers post that every composite number can be represented as product of prime factors. For example, $8=2*2*2$, $18=2*3*3$. In general you can say that any positive integer $N$ can be represented as follows:
$$N = p_1^{a_1}*p_2^{a_2}*….*p_k^{a_k} \text{ } \text{ } \forall \text{ } p_i \text{ are primes}$$

Important properties related to prime factors

  1. A divisor of a number is product of some or all of the prime factors of the number. For example, $6$ is a divisor of $18$ and hence, we can write $6 = 2*3$.
  2. We can find the number of divisors of a number if we know prime factorization of that number as follows:
    Suppose, $N = p_1^{a_1}*p_2^{a_2}*….*p_k^{a_k}$
    Now, we know that know divisor is just the product of some of the prime factors of the number. Hence, Number of divisors is equal to Number of combinations of prime factors which we can find easily as follows:

    Number of combinations of prime factors = 
                    Number of ways to choose p1* 
                    Number of ways to choose p2*
                                   .
                                   .
                                   . 
                    Number of ways to choose pk
    

    Since, we can choose $p_i$ as $p_i^0$, $p_i^1$, $p_i^2$, … or $p_i^{a_i}$, Number of ways to choose $p_i$ will be equal to $(a_i+1)$.
    Hence, Number of prime divisors will be equal to
    $$(a_1+1)*(a_2+1)*(a_3+1)*…*(a_k+1) $$
    For example, number of divisors of $18 = 3^2*2^1$ is $(2+1)*(1+1) = 6$. You can manually confirm that divisors of $18$ are $1, 2, 3, 6, 9, 19$.
    This is one of the most important results related to divisors which will be come handy many times in competitive programming. There are some more results such as sum and product of all divisors of a number but I am not discussing them right now as they are not of much use.

  3. If $F(X)$ denotes number of divisors of a number, then, $F(P*Q) = F(P)*F(Q)$, where $P$, $Q$ are co-prime. For example, $F(18) = F(9)*F(2) = 3*2 = 6$.
  4. There is at most one prime factor greater than $\sqrt{N}$ of a number $N$ because if there were two such prime factors, then, number should be greater than $N$. Similarly, we can say that there are at most two prime factors greater than $N^{1/3}$.

Okay! now it’s time to discuss some algorithm related to prime factors, counting of divisors.

Trial Division Algorithm for Prime Factorisation

This is one of the most basic algorithm of prime factorisation. It can be used to find distinct prime factors, number of divisors. The algorithm is follows:

  1. Iterate from $i=2$ to $\sqrt{N}$.
  2. If some $i$ divides $N$, then, keep dividing $N$ by $i$ until it divides $N$. Keep count of number of times $i$ divided $N$.
  3. After all the iterations, if $N>1$, then, this remaining $N$ will also be a prime factor of original $N$.

Now one question which will come into mind is how above algorithm is producing prime factors? Let me explain how. So, we starts from $i=2$ and if $2$ divides $N$, then, we are dividing $N$ by $2$ until it is no longer possible to do so. The end result will be elimination of factor of $2$ from $N$. Hence, no further composite number multiple of $2$ can divide $N$ now. We repeat the same approach for $i=3$ and eliminate factor of $3$. Now, when $i=4$, it is no longer possible for $i$ to divide $N$ as explained before. Repeating these steps for $i\leq\sqrt{n}$ will produce all the prime factors of $N$ which are not greater than $\sqrt{n}$.
If all prime factors were less than or equal to $\sqrt{n}$, then, $N$ will become $1$ after the iterations are over. Otherwise, the $N$ left will be the only prime factor of original $N$ which is greater than $\sqrt{n}$ as explained in property $4$.
This completes the intuitive proof of trial division algorithm for Prime Factorisation. Let’s see the code for this algorithm which you can directly use in competitive programming contests.

vector<pair<int, int> > trial_division(int n) {
	vector<pair<int, int> > pf;
	for (int i=2; i*i<=n; i++) {
		int count = 0;
		while (n%i==0) ++count, n/=i;
		if (count) pf.push_back({i, count});
	}
	if (n>1) pf.push_back({n, 1});
	return pf;
}

 

Optimizing Trial Division Algorithm for Prime Factorisation

Above algorithm involves unnecessary iterations over many composite numbers. Hence, for a number as large as $10^{12}$, it will take $10^6$ steps. Now, there are about $78498$ prime numbers less than $10^6$ which means that we are taking almost $10$ times steps more than required. Therefore, it will be wise for us to pre-compute all the prime numbers less than $10^6$ to answer multiple queries. You can find all the prime numbers less than $n$ efficiently by using seive of eratosthenes.  Below is the code for above prime factors algorithm:

vector<int> prime;

void sieve(int n) {
    bool isPrime[n+1];
    for (int i=1; i<=n; i++) isPrime[i] = 1;
    isPrime[1] = 0;
    for (int i=2; i<=n; i++) {
        // assert isPrime == True
        if (!isPrime[i]) continue;
        /* j*(i-1) is a factor of (i-1) and was covered before
           Therefore start from i*i */
        for (int j=i*i; j<=n; j+=i)
            if (isPrime[j]) isPrime[j] = 0;
    }
    for (int i=1; i<=n; i++) if (isPrime[i]) prime.push_back(i);
}

vector<pair<int, int> > optimized_trial_division(int n) {
    vector<pair<int, int> > pf;
    for (auto p : prime) {
        if (p*p > n) break;
        int count = 0;
        while (n%p==0) ++count, n/=p;
        if (count) pf.push_back({p, count});
    }
    if (n>1) pf.push_back({n, 1});
    return pf;
}

 

Number of divisors in $O(N^{1/3})$ (Fast Trick for CP)

This algorithm uses the extra result I discussed in property $4$ that there can be at most 2 prime factors greater than $N^{1/3}$. Let’s see the algorithm now.

  1. Iterate from $i=2$ to $N^{1/3}$.
  2. If some $i$ divides $N$, then, keep dividing $N$ by $i$ until it divides $N$. Keep count of number of times $i$ divided $N$.
  3. Now, if $N$ left is $1$, then, there are $0$ prime factors greater than $N^{1/3}$. Otherwise, there are $3$ cases possible.
    1. Exactly $1$ prime factor greater than $N^{1/3}$ with frequency $1$ – It will contribute factor $(1+1)$ to number of divisors.
    2. Another case is Exactly $1$ prime factor greater than $N^{1/3}$ with frequency $2$ – It will contribute factor $(2+1)$ to number of divisors.
    3. Exactly $2$ prime factors greater than $N^{1/3}$ with frequency $1$ – It will contribute factor $(1+1)*(1+1)$ to number of divisors.

    You can check for yourself that there cannot be any other case which satisfy property $4$. Now, for first case, we have to do Primality Test of $N$ which we can do by using Miller-Rabin test. Second case involves checking for perfect square which is quite easy. If first $2$ cases fails, then, third is automatically true.

Clearly, Miller-Rabin and square root testing are logarithmic algorithms and therefore, major time consuming operation is step $2$ which takes $O(N^{1/3})$ time. You can assure yourself of the fact that you cannot use this algorithm for prime factorisation as there is no way to find 2 prime factors greater than $N^{1/3}$ in $O(N^{1/3})$ time. Please read about millet-rabin on my blog or else you won’t understand the commented code. Below is the code for above algorithm:

vector<int> prime;

bool expo_mod(int x, int n, int m) {
    if (n==0) return 1;
    int y = expo_mod(x, n/2, m)%m;
    y = (y*y)%m;
    if (n%2) return (y*x)%m;
    return y;
}

bool miller_rabin_test(int n) {
    // Finding d
    int d = n-1;
    while (d%2 == 0)  d/=2;
    
    for (auto a : a_for_miller_rabin_and_fermat) {
        // assert a<n
        if (a>=n) break;
        // assert (n, a are coprime)
        if (__gcd(a, n) > 1) return false;
        
        int expo_d = expo_mod(a, d, n);
        // check for this a is over if condition 1 is true
        if (expo_d==1) continue;
        // check for condition 2
        bool ok = false;
        while (d != n-1) {
            expo_d = (expo_d * expo_d) % n, d *= 2;
            // Condition 2 satisfied
            if (expo_d == n-1) {
                ok = true;
                break;
            }
        }
        // Miller-rabin failed for this a
        if (!ok) return false;
    }
    // All passed
    return true;
} 

int number_of_divisors(int n) {
    int divisors = 1;
    for (auto p : prime) {
        if (p*p*p > n) break;
        int count = 0;
        while (n%p==0) ++count, n/=p;
        divisors *= (count+1);
    }
    if (n!=1) {
        if (miller_rabin_test(n)) divisors *= 2;
        else if (sqrt(n)*sqrt(n) == n) divisors *= 3;
        else divisors *= 4;
    }
    return divisors;
}

Logarithmic Prime Factorisation Algorithm For Multiple Queries

This is the most efficient Prime Factors Algorithm that you will use in Competitive Programming. Though, there are more efficient algorithms such Pollard’s Rho algorithm but you will rarely encounter them in competitive programming.
Suppose that you know the Smallest Prime Factor (SPF) of all numbers from $2$ to $N$. Now, for finding prime factorisation of $N$, you can simply divide $N$ by its $SPF(n)$ until $N$ becomes $1$.
For $N=18$, $SPF(18) = 2$.
Now, after $N$ is divided by $2$, $N$ will become $9$.
Also, $SPF(9) = 3$.
Divide $N$ by $3$, $N$ will become $3$.
Again, $SPF(3) = 3$
Divide $N$ by $3$, $N$ will become $1$.
Hence, Prime factors of $18$ are $2, 3, 3$.
You can see that above algorithm runs in $O(\log{N})$ because in worst case all the prime factors of $N$ are $2$ and our algorithm will perform $\log{N}$ iterations to make $N=1$.
For finding SPF in $O(1)$ time, we have to pre-compute SPFs of all the numbers from $2$ to $N$. We will use Seive of Eratosthenes for finding SPF. I will advice you to thoroughly read Seive of Eratosthenes before moving forward.
So, I guess all of you remember the step of marking multiples of a prime in seive of Eratosthenes. Let’s say some number $x$ was marked as multiple of some prime $p$. Since, $x$ was unmarked until $p$ comes to the picture means that none of the prime less than $p$ divided $x$. Therefore, $p$ should be the SPF of $x$. Also, SPF of a prime $p$ is $p$ itself because $1$ is not a prime number. Below is the code for this prime factors algortihm:

#define MAX 892

int SPF[MAX];

void sieve(int n=MAX) {
    bool isPrime[n+1];
    for (int i=1; i<=n; i++) isPrime[i] = 1;
    isPrime[1] = 0;
    for (int i=2; i<=n; i++) {
        // assert isPrime == True
        if (!isPrime[i]) continue;
        /* j*(i-1) is a factor of (i-1) and was covered before
           Therefore start from i*i */
        SPF[i] = i;
        for (int j=i*i; j<=n; j+=i)
            if (isPrime[j]) isPrime[j] = 0, SPF[j] = i;
    }
}

vector<pair<int, int> > prime_factorisation_logn(int n) {
    vector<pair<int, int> > pf;
    while (n!=1) {
        int p = SPF[n], count = 0;
        while (n%p==0) n/=p, ++count;
        pf.push_back({p, count});
    }
    return pf;
}

 
So, I have finished my work. Now, it is your turn to go to codechef or codeforces and search for problems with algorithm, prime factors, seive tag and start solving them. Thank you guys for reading so far.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: