← Oracle questions

Find the factor tree of a given number

Filed under Oracle

Free read 3 of 3

Iterate from 2 up to sqrt(N) to find the first divisor.

The question

Construct a factor tree for a given integer, recursively breaking it down into its factors until prime factors are reached.

Constraints

  • Input integer > 1
  • Output structure should represent the hierarchy
  • Handle prime numbers

Examples

Input
12
Output
(3, (2, 2))
Why
12 splits into 3 and 4; 4 splits into 2 and 2.

Approach

  1. Iterate from 2 up to sqrt(N) to find the first divisor.

Solution

O(sqrt(N)) time, O(log N) space

Python
def get_factor_tree(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return (i, get_factor_tree(n // i))
    return n

Tips

  • What they are testing: Test with prime numbers and highly composite numbers.
  • Common mistake: Failing to stop recursion at prime numbers, leading to infinite loops.

Related Oracle questions

Collected from public candidate posts and coding forums. Updated Nov 2026.