Print all Divisors

Easy

Only walk up to the square root

Problem

Given a positive integer n, print all of its divisors in ascending order.

In simple words

Try every number up to n and keep the ones that divide it evenly.

The idea

Divisors come in pairs: if i divides n then so does n/i, and one of that pair is always at most √n. So looping i to √n and recording both members of each pair finds every divisor in O(√n) instead of O(n).

The trick

When i * i == n, record i only once or you will duplicate the square root.
Collect the pairs and sort at the end if the output must be ascending.

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.

←→stepspaceplay

1/2

Optimal

timeO(sqrt n)spaceO(sqrt n)

1for i in 1..sqrt(n):2  if n % i == 0:3    add i4    if i != n / i: add n / i5sort and print

Input

array: [36]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 6
Output:: [1, 2, 3, 6]
Explanation:: 1, 2, 3 and 6 all divide 6 with no remainder.

Example 2

Input:: n = 12
Output:: [1, 2, 3, 4, 6, 12]
Explanation:: The divisors of 12 are 1, 2, 3, 4, 6, 12.

Example 3

Input:: n = 7
Output:: [1, 7]
Explanation:: 7 is prime, so only 1 and 7 divide it.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.