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.
Please use as a reference.

There are some similar articles and will add contents, so please read more other articles.

What is a divisor?
Two ways to find them
1. Simply divide
Example of implementation
2. Marking the divisors
Implementation example
Summary

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\).

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\).

\(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\).

Thank you for reading and please spread this blog if you like.

If you have any comment, please let me know from the e-mail address below or the CONTACT on the menu bar.
tsunetthi(at)gmail.com
Please change (at) to @.

Or you can also contact me via twitter (@warotan3)