# Divisibility

Authors: Darren Yao, Michael Cao, Andi Qu, and Kevin Sheng

Contributor: Juheon Rhee

Using the information that one integer evenly divides another.

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

Resources | ||||
---|---|---|---|---|

AoPS | practice problems, set focus to number theory! | |||

AoPS | good book |

## Resources

Resources | ||||
---|---|---|---|---|

IUSACO | module is based off this | |||

David Altizio | ||||

CPH | ||||

PAPS | ||||

MONT | ||||

AoPS | nice proofs and problems |

## Prime Factorization

A positive integer $a$ is called a **divisor** or a **factor** of a non-negative
integer $b$ if $b$ is divisible by $a$, which means that there exists some
integer $k$ such that $b = ka$. An integer $n > 1$ is **prime** if its only
divisors are $1$ and $n$. Integers greater than $1$ that are not prime are
**composite**.

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

where the $p_i$ are distinct primes and the $a_i$ are positive integers.

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

C++

vector<int> factor(int n) {vector<int> ret;for (int i = 2; i * i <= n; i++) {while (n % i == 0) {ret.push_back(i);n /= i;}}if (n > 1) { ret.push_back(n); }return ret;}

Java

List<Integer> factor(int n) {List<Integer> factors = new ArrayList<>();for (int i = 2; i * i <= n; i++) {while (n % i == 0) {factors.add(i);n /= i;}}if (n > 1) { factors.add(n); }return factors;}

Python

from typing import Listdef factor(n: int) -> List[int]:ret = []i = 2while i * i <= n:while n % i == 0:ret.append(i)n //= ii += 1if n > 1:ret.append(n)return ret

This algorithm runs in $\mathcal{O}(\sqrt{n})$ time, because the for loop checks divisibility for at most $\sqrt{n}$ values. Even though there is a while loop inside the for loop, dividing $n$ by $i$ quickly reduces the value of $n$, 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 = 252$.

$i$ | $n$ | $\texttt{ret}$ |
---|---|---|

$2$ | $252$ | $\{\}$ |

$2$ | $126$ | $\{2\}$ |

$2$ | $63$ | $\{2, 2\}$ |

$3$ | $21$ | $\{2, 2, 3\}$ |

$3$ | $7$ | $\{2, 2, 3, 3\}$ |

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

Focus Problem – try your best to solve this problem before continuing!

### Solution - Counting Divisors

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

C++

#include <iostream>using namespace std;int main() {int n;cin >> n;for (int q = 0; q < n; q++) {int x;int div_num = 0;

Java

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Divisors {public static void main(String[] args) throws IOException {BufferedReader read =new BufferedReader(new InputStreamReader(System.in));int queryNum = Integer.parseInt(read.readLine());StringBuilder ans = new StringBuilder();

Python

### Warning!

Due to Python's big constant factor, the following code TLEs on quite a few test cases.

ans = []for _ in range(int(input())):div_num = 0x = int(input())i = 1while i * i <= x:if x % i == 0:div_num += 1 if i**2 == x else 2i += 1ans.append(div_num)print("\n".join(str(i) for i in ans))

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

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

Then the number of divisors of $x$ is simply $(a_1 + 1) \cdot (a_2 + 1) \cdots (a_k + 1)$.

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

$x$ can have $\mathcal{O}(\log x)$ distinct prime factors, so if we can find the prime factorization of $x$ efficiently, we can use it with the above property to answer queries in $\mathcal{O}(\log x)$ time instead of the previous $\mathcal{O}(\sqrt x)$ time.

Here's how we find the prime factorization of $x$ in $\mathcal{O}(\log x)$ time with $\mathcal{O}(x \log x)$ preprocessing:

- For each $k \leq 10^6$, find any prime number that divides $k$. To find this, we can use the Sieve of Eratosthenes which runs in $\mathcal{O}(n \log n)$, where $n$ is the larger numbers we consider. There's also a version of the sieve that runs in linear time, but we won't be needing it.
- We can find the prime factorization of $x$ by repeatedly dividing it by the prime numbers we calculated earlier until $x = 1$.

Using this method gives us the following code:

C++

#include <iostream>using namespace std;const int MAX_N = 1e6;// max_div[i] contains the largest prime that goes into iint max_div[MAX_N + 1];int main() {for (int i = 2; i <= MAX_N; i++) {

Java

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Divisors {private static final int MAX_N = (int)Math.pow(10, 6);public static void main(String[] args) throws IOException {// maxDiv[i] contains the largest prime that can divide iint[] maxDiv = new int[MAX_N + 1];for (int i = 2; i <= MAX_N; i++) {

Python

MAX_N = 10**6# max_div[i] contains the largest prime that can go into imax_div = [0 for _ in range(MAX_N + 1)]for i in range(2, MAX_N + 1):if max_div[i] == 0:for j in range(i, MAX_N + 1, i):max_div[j] = ians = []

## GCD & LCM

### GCD

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

This algorithm can be implemented with a recursive function as follows:

Java

public int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

C++

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

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

.

In C++17, there exists `std::gcd`

and `std::lcm`

in the
`<numeric>`

header, so there's no
need to code your own GCD and LCM if you're using that version.

Python

def gcd(a: int, b: int) -> int:return a if b == 0 else gcd(b, a % b)

You won't have to actually implement this in-contest,
as the built-in `math`

library has a `gcd`

and `lcm`

function.

This function runs in $\mathcal{O}(\log ab)$ time because $a\le b \implies b\pmod a <\frac{b}{2}$.

The worst-case scenario for the Euclidean algorithm is when $a$ and $b$ are consecutive Fibonacci numbers $F_n$ and $F_{n + 1}$. In this case, the algorithm will calculate that $\gcd(F_n, F_{n + 1}) = \gcd(F_{n - 1}, F_n) = \dots = \gcd(0, F_1)$. This takes a total of $n+1$ calls, which is proportional to $\log \left(F_n F_{n+1}\right)$.

### LCM

The **least common multiple (LCM)** of two integers $a$ and $b$ is the smallest
integer divisible by both $a$ and $b$. The LCM can be calculated with the GCD
using this property:

### Warning!

Coding $\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`

in C++ and Java 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`

.

Also, these two functions are associative, meaning that 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,

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

AC | Easy | ## Show TagsPrime Factorization | |||

CF | Easy | ## Show TagsDivisibility, Modular Arithmetic | |||

CF | Easy | ## Show TagsNT | |||

CF | Easy | ## Show TagsDivisibility | |||

CSES | Normal | ||||

CF | Normal | ## Show TagsPrime Factorization | |||

CC | Normal | ## Show TagsDivisibility | |||

CSES | Hard | ||||

CF | Hard | ## Show TagsDivisibility |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!