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?
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
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
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\),
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;
This method can catch all divisors with calculation time
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)