Efficiently getting all divisors of a given number

c++ algorithm math factorization
zangw picture zangw · Nov 5, 2014 · Viewed 104.4k times · Source

According to this post, we can get all divisors of a number through the following codes.

for (int i = 1; i <= num; ++i){
    if (num % i == 0)
        cout << i << endl;
}

For example, the divisors of number 24 are 1 2 3 4 6 8 12 24.

After searching some related posts, I did not find any good solutions. Is there any efficient way to accomplish this?

My solution:

  1. Find all prime factors of the given number through this solution.
  2. Get all possible combinations of those prime factors.

However, it doesn't seem to be a good one.

Answer

Yu Hao picture Yu Hao · Nov 5, 2014

Factors are paired. 1 and 24, 2 and 12, 3 and 8, 4 and 6.

An improvement of your algorithm could be to iterate to the square root of num instead of all the way to num, and then calculate the paired factors using num / i.

Related questions

Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
Finding square root without using sqrt function?

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++ #include <iostream> using namespace std; double …

Read More