AlgoMaster Logo

Print All Factors of a Number

Last Updated: June 7, 2026

easy
4 min read

Understanding the Problem

Finding the factors of a number is a building block for checking whether a number is prime, computing the greatest common divisor, and reducing fractions to their simplest form.

You receive a positive integer n, and you return every integer that divides it cleanly, listed from smallest to largest. For n = 12, the answer is [1, 2, 3, 4, 6, 12]. Every number in that list divides 12 with no remainder, and 1 and 12 are always included because 1 divides everything and every number divides itself.

The remainder operator % is the tool that tells you whether one number divides another. If n % i == 0, then i is a factor of n. The two approaches below differ only in how many candidates they test.

Key Constraints:

  • 1 <= n → The input is always positive, so you never deal with zero or negative numbers. The factor of the smallest input, 1, is just [1], since 1 divides itself and nothing smaller exists.
  • n <= 10^6 → The value can reach one million. A scan from 1 to n performs up to a million checks, which is fine for a single call but wasteful. Scanning only up to the square root reduces this to about a thousand checks.

Approach 1: Linear Scan

Intuition

Test every candidate. Walk from 1 up to n, and for each value i, check whether n % i equals 0. If it does, i is a factor, so add it to the list.

Walking in increasing order leaves the factors already sorted. No extra sorting step is needed.

Algorithm

  1. Create an empty list to hold the factors.
  2. Loop i from 1 to n inclusive.
  3. If n % i == 0, append i to the list.
  4. Return the list once the loop finishes.

Example Walkthrough

Input:

12
n

Test each value from 1 to 12. The checks that succeed are 12 % 1, 12 % 2, 12 % 3, 12 % 4, 12 % 6, and 12 % 12, all of which leave a remainder of 0. The values 5, 7, 8, 9, 10, and 11 leave a nonzero remainder, so they are skipped. The factors collected in order form the result:

0
1
1
2
2
3
3
4
4
6
5
12
result

Code

The linear scan is easy to read, but it tests every number up to n. For n = 10^6, that is a million checks. The same factors can be found while testing far fewer candidates.

Approach 2: Scan to Square Root

Intuition

Factors come in pairs. If i divides n, then n / i also divides n, and the two multiply back to n. For n = 12, the pairs are 1 and 12, 2 and 6, and 3 and 4. One member of each pair is at most the square root of n, and the other is at least the square root. So scanning up to the square root discovers every factor, since each small factor reveals its larger partner.

This drops the work from n checks to about the square root of n checks. For n = 10^6, that is roughly a thousand checks instead of a million.

The pairs are discovered out of order: the partner n / i belongs much later in the sorted output. The fix is to collect the small factors in one list and the partners in a second list, then append the partners in reverse so the final array stays sorted ascending. When i * i == n, the factor and its partner are the same number, as with 4 for n = 16, so record it only once to avoid a duplicate.

Algorithm

  1. Create two lists, small for factors up to the square root and large for their partners.
  2. Loop i starting at 1 while i * i <= n.
  3. If n % i == 0, then i is a factor. Append i to small. If i != n / i, append n / i to large.
  4. After the loop, append the contents of large in reverse order to small.
  5. Return small, which now holds every factor in increasing order.

Example Walkthrough

Input:

12
n

Loop i while i * i <= 12, so i runs from 1 to 3. At i = 1, 12 % 1 == 0, giving the pair 1 and 12. At i = 2, 12 % 2 == 0, giving the pair 2 and 6. At i = 3, 12 % 3 == 0, giving the pair 3 and 4. The small factors collected are [1, 2, 3] and the partners are [12, 6, 4].

Appending the partners in reverse to the small factors gives [1, 2, 3] followed by [4, 6, 12], which is the sorted result:

0
1
1
2
2
3
3
4
4
6
5
12
result

Code