Find all divisors of a natural number | Set 1 - GeeksforGeeks
Given a natural number n, print all distinct divisors of it.
http://www.geeksforgeeks.org/find-all-divisors-of-a-natural-number-set-2/
Read full article from Find all divisors of a natural number | Set 1 - GeeksforGeeks
Given a natural number n, print all distinct divisors of it.
Input: n = 100 Output: 1 2 4 5 10 20 25 50 100
Note that this problem is different from finding all prime factors.
If we look carefully, all the divisors are present in pairs. For example if n = 100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10)
Using this fact we could speed up our program significantly.
We, however have to be careful if there are two equal divisors as in case of (10, 10). In such case we’d print only one of them.
We, however have to be careful if there are two equal divisors as in case of (10, 10). In such case we’d print only one of them.
Time Complexity : O(sqrt(n))
void printDivisors(int n){ // Note that this loop runs till square root for (int i=1; i<=sqrt(n)+1; i++) { if (n%i==0) { // If divisors are equal, print only one if (n/i == i) printf("%d ", i); else // Otherwise print both printf("%d %d ", i, n/i); } }}void printDivisors(int n){ for (int i=1;i<=n;i++) if (n%i==0) printf("%d ",i);}
Yes! the output is not in a sorted fashion which we had got using brute-force technique.
How to print the output in sorted order?
If we observe the output which we had got, we can analyze that the divisors are printed in a zig-zag fashion (small, large pairs). Hence if we store half of them then we can print then in a sorted order.
If we observe the output which we had got, we can analyze that the divisors are printed in a zig-zag fashion (small, large pairs). Hence if we store half of them then we can print then in a sorted order.
void printDivisors(int n){ // Vector to store half of the divisors vector<int> v; for (int i=1;i<=sqrt(n)+1;i++) { if (n%i==0) { if (n/i == i) // check if divisors are equal printf("%d ", i); else { printf("%d ", i); // push the second divisor in the vector v.push_back(n/i); } } } // The vector will be printed in reverse for (int i=v.size()-1; i>=0; i--) printf("%d ", v[i]);}