# W2 Notes: Number Theory 1
[ToC]
## Number Theory: Finding Divisors, Number and Sum of Divisors, and Primality Test
You are given four problems, all concerning the positive divisors (factors) of a positive integer $n$:
1. Find **all the divisors** of $n$.
1. Find the **number (count) of all the divisors** of $n$.
1. Find the **sum of all the divisors** of $n$.
1. Find if $n$ is a [prime number](https://en.wikipedia.org/wiki/Prime_number), i.e., test it for **primality**.
Let's first come up with brute-force solutions for them. Eventually, we'll see that it's possible to solve all four of them more efficiently using a neat pattern of divisors.
### Brute-force solutions
- Brute-force implementation for *divisors*:
```cpp=
vector<int> divisors(int n) {
vector<int> div;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
div.push_back(i);
}
}
return div;
}
```
- Brute-force implementation for *number of divisors (NOD)*:
```cpp=
int NOD(int n) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
++cnt;
}
}
return cnt;
}
```
- Brute-force implementation for *sum of divisors (SOD)*:
```cpp=
int SOD(int n) {
int sum = 0;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
```
- Brute-force implementation for *primality test*:
```cpp=
bool is_prime(int n) {
for (int i = 2; i < n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
```
- Time coplexity: $O(n)$
- Is this complexity good enough if $n \geq 10^{9}$? Or if $1 \leq n \leq 10^5$ but you have to answer $t$ ($1 \leq t \leq 10^{4}$) cases per test? --- NO
### Better solutions
- **Observation:** If $x$ is a divisor (factor) of $n$, then $n / x$ must also be a divisor of $n$. That is, $x | n \Rightarrow (n / x) | n$. Let $y = n / x \Rightarrow x \cdot y = n$. Thus, for each divisor $x$ of $n$, we get a *complementary divisor pair* $(x, y) = (x, n / x)$.
- If $x = \sqrt n$, then $y = \sqrt n$ must also hold, otherwise $x \cdot y = n$ would not be possible. For the same reason,
- if $x < \sqrt n$, then $y > \sqrt n$ must also hold, and
- if $x > \sqrt n$, then $y < \sqrt n$ must also hold.
This essentially means that **if we find all the divisors of $n$ that are less than or equal to $\sqrt n$, we also get all of its divisors greater than or equal to $\sqrt n$** at the same time. Thus, we can see that the number of divisors of $n$ is always **less than $2\sqrt n$**, which is expressed in the big-O notation as $O(2\sqrt n) \sim O(\sqrt n)$. Hence, we only need to find the divisors up to $\sqrt n$ to exhaustively search all the divisors.
- **Example:** Let's iterate over the sequence of divisors $a = [1, 2, 3, 4, 6, 9, 12, 18, 36]$ of $n = 36$, and simultaneously generate another sequence $b$ such that $a_i \cdot b_i = n \Rightarrow b_i = n / a_i$.
| $a_i$ | $b_i = n / a_i$ |
|--------|-----------------|
| $1$ | $36$ |
| $2$ | $18$ |
| $3$ | $12$ |
| $4$ | $9$ |
| $6$ | $6$ |
| $9$ | $4$ |
| $12$ | $3$ |
| $18$ | $2$ |
| $36$ | $1$ |
Notice that $b = reverse(a)$, and the sequence of the unordered pairs $(a_i, b_i)$ is symmetric about the point where $a_i = \sqrt n$. Up to that point, all the divisors of $36$ can be found thus:
$36 \\
= 1 \cdot 36 \\
= 2 \cdot 18 \\
= 3 \cdot 12 \\
= 4 \cdot 9 \\
= 6 \cdot 6$
- $O(\sqrt n)$ implementation for *divisors*:
- Simpler implementation:
```cpp=
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 (n / i != i) {
div.push_back(n / i);
}
}
}
// Sort the divisors if needed. Note that this
// changes the complexity to O(sqrt(n) * log(sqrt(n))),
// because `std::sort` on an array of length n takes
// O(n * log(n)) time.
sort(div.begin(), div.end());
return div;
}
```
- More efficient implementation:
```cpp=
vector<int> divisors(int n) {
vector<int> div;
vector<int> buf; // buffer (temp. storage)
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
div.push_back(i);
buf.push_back(n / i);
}
}
int from = buf.front() == div.back() ? 1 : 0;
for (int i = buf.size() - 1; i >= from; --i) {
div.push_back(buf[i]);
}
return div;
}
```
- $O(\sqrt n)$ implementation for *number of divisors (NOD)*:
```cpp=
int NOD(int n) {
int cnt = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
++cnt;
if (n / i != i) {
++cnt;
}
}
}
return cnt;
}
```
- $O(\sqrt n)$ implementation for *sum of divisors (SOD)*:
```cpp=
int SOD(int n) {
int sum = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
++cnt;
if (n / i != i) {
++cnt;
}
}
}
return sum;
}
```
- $O(\sqrt n)$ implementation for *primality test*:
```cpp=
bool is_prime(int n) {
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
```
## Number Theory: Modular Arithmetic
The [Wikipedia article](https://en.wikipedia.org/wiki/Modular_arithmetic) says:
> In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus.
Make sure to learn about *congruence relations* from [this section](https://en.wikipedia.org/wiki/Modular_arithmetic#Congruence) of that article.
For this lesson, let $M$ be the modulus.
- **Modular Addition:**
$\begin{align*}
(a + b) \mod M \\
= ((a \mod M) + (b \mod M)) \mod M
\end{align*}$
- **Modular Subtraction:**
$\begin{align*}
(a - b) \mod M \\
= ((a \mod M) - (b \mod M)) \mod M
\end{align*}$
- **Modular Multiplication:**
$\begin{align*}
(a \cdot b) \mod M \\
= ((a \mod M) \cdot (b \mod M)) \mod M
\end{align*}$
- The case for modular division is different, and is beyond the scope of this class.
Sign in with Wallet
Connect another wallet