In order to find all the divisors of a number, we have the following approaches: First is Bruteforce, where we can divide the number starting from 2 and saving those which divide completely.
vector<int> find_all_divisors(int k)
{
vector<int> divisors;
for(int i = 2;i < k;i++)
if(k%i==0)
divisors.push_back(i);
return divisors;
}
However, the above approach takes O(n) time to complete, another approach can do this in O(√n), which iterates only till the square root of the number.
vector<int> find_all_divisors(int n)
{
vector<int> x;
int s = sqrt(n);
for(int i = 1;i <= s;i++)
{
if (n%i==0)
{
if (n/i == i) // check if divisors are equal
x.push_back(i);
else
{
x.push_back(i);
x.push_back(n/i);
}
}
}
x.push_back(n);
return x;
}
P.S.=> Above method does not give divisors in sorted order.
Wow such a cool trick
P.S. Also I've read somewhere that 1 and n are also divisors of n, aren't they?
But, sometimes it's better to have it predefined with criba :), depends on k
[deleted]