Divisors of a Number
EasyPair them up around the square root
Problem
Print all divisors of a number in ascending order.
Check numbers up to the square root; each divisor comes with its partner n/divisor.
The idea
Divisors come in pairs (i, n/i) and one of each pair is at most √n, so looping to √n finds them all in O(√n). Collect both members of each pair, taking care not to record a perfect square's root twice.
The trick
- Record i and n/i, but only once when i * i == n.
- Sort afterwards if ascending output is required.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — 36 Values: 36.
1for i in 1..sqrt(n):2 if n%i==0: add i; if i!=n/i: add n/i3sort and printInput
- array
- [36]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 12
- Output:
- [1, 2, 3, 4, 6, 12]
- Explanation:
- 1,2,3,4,6,12 all divide 12.
Example 2
- Input:
- n = 10
- Output:
- [1, 2, 5, 10]
- Explanation:
- 1,2,5,10.
Example 3
- Input:
- n = 7
- Output:
- [1, 7]
- Explanation:
- Prime → 1 and 7 only.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.