Блог пользователя rootn

Автор rootn, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Wow such a cool trick

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

[deleted]