All challenges
Medium 0 solved 0% acceptance

Prime Factorization

Break a number into its prime factors, listed from smallest to largest with repetition.

What you'll learn

  • Divide out each factor as many times as it occurs
  • Stop trial division once d × d exceeds what is left
  • Recognise that a leftover above 1 is a prime factor

Problem

Every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors (the fundamental theorem of arithmetic). For example, 360 = 2 × 2 × 2 × 3 × 3 × 5. Finding that list is called prime factorization.

Implement prime_factorization(n).

n can be as large as 10^12, so the classic approach is trial division: divide out 2 as long as you can, then 3, and so on. You only need to try divisors d while d × d ≤ the part of n that is still left; whatever remains above 1 at the end is itself prime. That keeps the work to about √n ≈ 10^6 steps even when n is a large prime or the product of two large primes.

Input

n: The number to factor.

Output

Return the prime factors of n in ascending order, repeating each prime as many times as it divides n, so that the product of the list is n. For n = 1 return an empty list. If n is prime, the list has the single element n.

Constraints

1 ≤ n ≤ 10^12

Examples

Example 1
Input:
n = 360

Expected output:
expected = [2, 2, 2, 3, 3, 5]
Input:
long long n = 360;

Expected output:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Input:
long n = 360;

Expected output:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

Explanation

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, so the answer is [2, 2, 2, 3, 3, 5].

Example 2
Input:
n = 97

Expected output:
expected = [97]
Input:
long long n = 97;

Expected output:
std::vector<long long> expected = {97};
Input:
long n = 97;

Expected output:
long[] expected = new long[] {97};

Explanation

No prime up to √97 ≈ 9.8 (2, 3, 5, 7) divides 97, so it is prime and the answer is [97].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Divide by 2 while you can, then move to 3, 5, 7, and so on.

Hint 2

Shrink n each time you find a factor, and compare d × d with the shrunken n.

Hint 3

If something greater than 1 is left after the loop, it is the largest prime factor.

Expected complexity

O(√n) time, O(log n) extra space for the result

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.