Find the factor tree of a given number
Filed under Oracle
Free read 3 of 3Iterate 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
Iterate from 2 up to sqrt(N) to find the first divisor.
If a divisor is found, return a node containing the divisor and the result of recursing on N/divisor.
If no divisor is found, the number is prime; return the number itself.
Solution
O(sqrt(N)) time, O(log N) space
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.