PrevNext
Rare
 0/5

Divisibility

Authors: Darren Yao, Michael Cao, Andi Qu

Using the information that A is a factor of B

If you've never encountered any number theory before, AoPS is a good place to start.

Resources
AoPSpractice problems, set focus to number theory!
AoPSgood book

Resources

Prime Factorization

Focus Problem – read through this problem before continuing!

A number aa is called a divisor or a factor of a number bb if bb is divisible by aa, which means that there exists some integer kk such that b=kab = ka. Conventionally, 11 and nn are considered divisors of nn. A number n>1n > 1 is prime if its only divisors are 11 and nn. Numbers greater than (1) that are not prime are composite.

Every number has a unique prime factorization: a way of decomposing it into a product of primes, as follows:

n=p1a1p2a2pkakn = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_k}^{a_k}

where the pip_i are distinct primes and the aia_i are positive integers.

Now, we will discuss how to find the prime factorization of an integer.

C++

1vector<int> factor(int n) {
2 vector<int> ret;
3 for (int i = 2; i * i <= n; i++) {
4 while (n % i == 0) {
5 ret.push_back(i);
6 n /= i;
7 }
8 }
9 if (n > 1) ret.push_back(n);
10 return ret;

Java

1ArrayList<Integer> factor(int n) {
2 ArrayList<Integer> factors = new ArrayList<>();
3 for (int i = 2; i * i <= n; i++) {
4 while (n % i == 0) {
5 factors.add(i);
6 n /= i;
7 }
8 }
9 if (n > 1) factors.add(n);
10 return factors;

Python

1def factor(n):
2 ret = []
3 i = 2
4 while i * i <= n:
5 while n % i == 0:
6 ret.append(i)
7 n //= i
8 i += 1
9 if n > 1:
10 ret.append(n)

This algorithm runs in O(n)O(\sqrt{n}) time, because the for loop checks divisibility for at most n\sqrt{n} values. Even though there is a while loop inside the for loop, dividing nn by ii quickly reduces the value of nn, which means that the outer for loop runs less iterations, which actually speeds up the code.

Let's look at an example of how this algorithm works, for n=252n = 252.

Example

At this point, the for loop terminates, because ii is already 3 which is greater than 7\lfloor \sqrt{7} \rfloor. In the last step, we add 77 to the list of factors vv, because it otherwise won't be added, for a final prime factorization of {2,2,3,3,7}\{2, 2, 3, 3, 7\}.

Solution - Counting Divisors

The most straightforward solution is just to do what the problem asks us to do - for each xx, find the number of divisors of xx in O(x)O(\sqrt x) time.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(0);
6 cin.tie(0);
7 int n;
8 cin >> n;
9 while (n--) {
10 int x, ans = 0;

Java

1import java.io.*;
2import java.util.*;
3
4public class Main {
5 static int solve(int n) {
6 int divisors = 0;
7 for (int i = 1; i * i <= n; i++) {
8 if (n % i == 0) {
9 if (i * i == n) divisors++;
10 else divisors += 2;

This solution runs in O(nx)O(n \sqrt x) time, which is just fast enough to get AC. However, we can actually speed this up to get an O((x+n)logx)O((x + n) \log x) solution!

First, let's discuss an important property of the prime factorization of a number. Consider:

x=p1a1p2a2pkakx = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_k}^{a_k}

Then the number of divisors of xx is simply (a1+1)(a2+1)(ak+1)(a_1 + 1) \cdot (a_2 + 1) \cdots (a_k + 1).

Why is this true? The exponent of pip_i in any divisor of xx must be in the range [0,ai][0, a_i] and each different exponent results in a different set of divisors, so each pip_i contributes ai+1a_i + 1 to the product.

xx can have O(logx)O(\log x) distinct prime factors, so if we can find the prime factorization of xx efficiently, we can answer queries in O(logx)O(\log x) time instead of the previous O(x)O(\sqrt x) time.

Here's how we find the prime factorization of xx in O(logx)O(\log x) time with O(xlogx)O(x \log x) preprocessing:

  • For each k106k \leq 10^6, find any prime number that divides kk.
    • We can use the Sieve of Eratosthenes to find this efficiently.
  • For each xx, we can then find the prime factorization by repeatedly dividing xx by a prime number that divides xx until x=1x = 1.

Alternatively, we can slightly modify the the prime factorization code above.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int max_div[1000001];
5
6int main() {
7 ios_base::sync_with_stdio(0);
8 cin.tie(0);
9 for (int i = 2; i <= 1000000; i++) {
10 if (!max_div[i]) {

Java

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

make java code consistent w/ C++ code ...

1import java.io.*;
2import java.util.*;
3
4public class Main {
5 static int solve(int n) {
6 int divisors = 1;
7 for (int i = 2; i * i <= n; i++) {
8 int ct = 0;
9 while (n % i == 0) {
10 ct++;
Optional

Apply the linear sieve.

GCD & LCM

GCD

The greatest common divisor (GCD) of two integers aa and bb is the largest integer that is a factor of both aa and bb. In order to find the GCD of two non-negative integers, we use the Euclidean Algorithm, which is as follows:

gcd(a,b)={ab=0gcd(b,amodb)b0\gcd(a, b) = \begin{cases} a & b = 0 \\ \gcd(b, a \bmod b) & b \neq 0 \\ \end{cases}

This algorithm is very easy to implement using a recursive function, as follows:

Java

1public int gcd(int a, int b){
2 if (b == 0) return a;
3 return gcd(b, a % b);
4}

C++

1int gcd(int a, int b){
2 if (b == 0) return a;
3 return gcd(b, a % b);
4}

For C++14, you can use the built-in __gcd(a,b).

Python

1def gcd(a, b):
2 if b == 0:
3 return a
4 return gcd(b, a % b)

This function runs in O(logab)O(\log ab) time because ab    b%a<b2a\le b \implies b\%a <\frac{b}{2}.

The worst-case scenario for the Euclidean algorithm is when aa and bb are consecutive Fibonacci numbers FnF_n and Fn+1F_{n + 1}. for an explanation). In this case, the algorithm will calculate gcd(Fn,Fn+1)=gcd(Fn1,Fn)==gcd(0,F1)\gcd(F_n, F_{n + 1}) = \gcd(F_{n - 1}, F_n) = \dots = \gcd(0, F_1). This means that finding gcd(Fn,Fn+1)\gcd(F_n, F_{n + 1}) takes n+1n + 1 steps, which is proportional to log(FnFn+1)\log \left(F_n F_{n+1}\right).

LCM

The least common multiple (LCM) of two integers aa and bb is the smallest integer divisible by both aa and bb. The LCM can easily be calculated from the following property with the GCD:

lcm(a,b)=abgcd(a,b)=agcd(a,b)b.\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}=\frac{a}{\gcd(a,b)}\cdot b.

Warning!

Coding lcm\text{lcm} as a * b / gcd(a, b) might cause integer overflow if the value of a * b is greater than the max size of the data type of a * b (e.g. the max size of int is around 2 billion). Dividng a by gcd(a, b) first, then multiplying it by b will prevent integer overflow if the result fits in an int.

If we want to take the GCD or LCM of more than two elements, we can do so two at a time, in any order. For example,

gcd(a1,a2,a3,a4)=gcd(a1,gcd(a2,gcd(a3,a4))).\gcd(a_1, a_2, a_3, a_4) = \gcd(a_1, \gcd(a_2, \gcd(a_3, a_4))).

Exercise: What's wrong with the following code?

1ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b,a%b); }
2ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }
3
4int main() { cout << lcm(1000000000,999999999); } // output: 1808348672

Solution

Problems

StatusSourceProblem NameDifficultyTagsSolution
ACEasy
Show Tags

Prime Factorization

Check AC
CSESNormal
CFNormal
Show Tags

Prime Factorization

CSESHard

Module Progress:

Give Us Feedback on Divisibility!

PrevNext