# 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 | |||
---|---|---|---|

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

AoPS | good book |

## Resources

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

IUSACO | module is based off this | ||

David Altizio | |||

CPH | |||

PAPS |

## Prime Factorization

Focus Problem – read through this problem before continuing!

A number $a$ is called a **divisor** or a **factor** of a number $b$ if $b$ is divisible by $a$, which means that there exists some integer $k$ such that $b = ka$. Conventionally, $1$ and $n$ are considered divisors of $n$. A number $n > 1$ is **prime** if its only divisors are $1$ and $n$. 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:

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 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 = 24 while i * i <= n:5 while n % i == 0:6 ret.append(i)7 n //= i8 i += 19 if n > 1:10 ret.append(n)

This algorithm runs in $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$.

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\}$.

### 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 $O(\sqrt x)$ time.

C++

1#include <bits/stdc++.h>2using namespace std;34int 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.*;34public 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(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) \log x)$ solution!

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

$x = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_k}^{a_k}$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 $O(\log x)$ distinct prime factors, so if we can find the prime factorization of $x$ efficiently, we can answer queries in $O(\log x)$ time instead of the previous $O(\sqrt x)$ time.

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

- For each $k \leq 10^6$, find any prime number that divides $k$.
- We can use the Sieve of Eratosthenes to find this efficiently.

- For each $x$, we can then find the prime factorization by repeatedly dividing $x$ by a prime number that divides $x$ until $x = 1$.

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

C++

1#include <bits/stdc++.h>2using namespace std;34int max_div[1000001];56int 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.

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

1import java.io.*;2import java.util.*;34public 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++;

Apply the linear sieve.

## 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 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 a4 return gcd(b, a % b)

This function runs in $O(\log ab)$ time because $a\le b \implies b\%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}$. for an explanation). In this case, the algorithm will calculate $\gcd(F_n, F_{n + 1}) = \gcd(F_{n - 1}, F_n) = \dots = \gcd(0, F_1)$. This means that finding $\gcd(F_n, F_{n + 1})$ takes $n + 1$ steps, 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 easily be calculated from the following property with the GCD:

### 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`

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(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; }34int main() { cout << lcm(1000000000,999999999); } // output: 1808348672

Solution

## Problems

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

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

CSES | Normal | ||||

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

CSES | Hard |