rootn's blog

All Divisors
By rootn, 6 years ago, In English

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.

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Wow such a cool trick

P.S. Also I've read somewhere that 1 and n are also divisors of n, aren't they?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

But, sometimes it's better to have it predefined with criba :), depends on k

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

[deleted]

→ Reply