# Find divisors, with some implementations

We sometimes need to list divisors in competitive programming.
Here, two ways to find them with some program source codes are given.

## What is a divisor?

In mathematics, a divisor of an integer $$n$$, also called a factor of $$n$$, is an integer $$m$$ that may be multiplied by some integer to produce $$n$$. (Wikipedia)
For example, the divisor of 6 is 1,2,3,6 and 12 is 1,2,3,4,6,12.

## Two ways to find them

There are variety of ways to list divisors.
Here, commonly used two ways are given.

### 1. Simply divide

From the definition of a divisor, if we try to calculate it, then

we can archive the numbers from 1~$$n$$ that the target number is divided

It takes $$O\left(n\right)$$ with naive implementation, but we will finally find $$O\left(\sqrt{n}\right)$$ calculation as follows.

First, the factors $$a,b$$ of $$n$$ can be represented as

$$\begin{eqnarray} n = a\times b. \end{eqnarray}$$

This equation shows if an integer $$a$$ is the divisor of $$n$$, then $$n/a$$ can also divide $$n$$.
Therefore, when we find a divisor above $$\sqrt{n}$$, the number has already gotten into the list as $$n/a$$.
This symmetry reduces the calculation time from $$O\left(n\right)$$ to $$O\left(\sqrt{n}\right)$$.

#### Example of implementation

The implementation is going to be like this;

vector<long long> find_divisor(long long n){
vector<long long> divs;
for(long long a = 2; a * a < n; a++){
if(n % a == 0){
divs.push_back(a);
if(a*a != n) divs.push_back(n/a);
}
}
return divs;
}

The vector divs has the factors of an integer $$n$$.
We should take care not to forget adding $$n/a$$.
This is needed when the two divisors are different, so a branch with an if statement is placed.
This code can list the divisors with $$O\left(\sqrt{n}\right)$$ calculation time.

### 2. Marking the divisors

We can also specify divisors by marking them.

First, we make a table from 1~$$n$$. marking the multiple from 1~$$n$$

Here, we take $$n = 10$$ as an example.

In the beginning, we consider $$a = 1$$ and mark the multiple of $$a$$, All numbers are marked because they are all the multiple of $$a = 1$$

Take a look! $$n = 10$$ is marked.
That is to say, 10 is a multiple of 1 and 1 is a divisor of 10.

Next, we do the same with $$a = 2$$. The multiples of $$a = 2$$ are marked.

$$n = 10$$ is marked again, so we find that $$a = 2$$ is also divide $$n = 10$$.

Repeating the above operation 3~$$n$$, we will finally get all factors of $$n$$.

For your information, $$a = 3$$ is not a divisor as the table is like this; 10 is not marked because 3 is not the factor of 10

This method can catch all divisors with calculation time

$$\begin{eqnarray} n+\frac{n}{2}+\frac{n}{3}+\cdots + \frac{n}{n} &=& \sum_{i = 1}^{n}\frac{n}{i} \\ &\simeq& O\left(n\log n\right). \end{eqnarray}$$

It is slower than the method 1 but there is some use.
This time we think of one integer but we sometimes need to list divisors of some integers by reusing the table.

#### Implementation example

vector<int> find_divisors_log(int n){
vector<int> ans;
for(int i = 2;i <= n; i++){
vector<bool> x(n+1,false);
for(int j = i;j <= n; j += i){
x[j] = true;
}
if(x[n]) ans.push_back(i);
}
return ans;
}

## Summary

Now, that’s all what I wanted to write.

This time, I summarized two ways of how to list divisors of an integer $$n$$.