Print Prime Factors of a Number

Hard

Divide out each factor as you find it

Problem

Print all prime factors of a number with their multiplicity.

In simple words

Keep dividing by the smallest factor until you reach 1.

The idea

Try divisors from 2 upward and, whenever one divides, keep dividing it out while recording it. Once the trial divisor passes √n, whatever remains above 1 is itself prime — which is why the loop can stop early.

The trick

Divide out each factor completely before moving on, to get multiplicities.
Stop the loop at √n; the leftover is a prime factor.
O(√n) per number.

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(1)

1for p from 2 while p*p<=n:2  while n%p==0: print(p); n/=p3if n>1: print(n)

Input

array: [60]

Output

answer: —

Check yourself

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

Examples

Example 1

Input:: n = 12
Output:: [2, 2, 3]
Explanation:: 12 = 2 x 2 x 3.

Example 2

Input:: n = 60
Output:: [2, 2, 3, 5]
Explanation:: 60 = 2 x 2 x 3 x 5.

Example 3

Input:: n = 13
Output:: [13]
Explanation:: 13 is prime.

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

Finished the walkthrough? Add it to your streak.