TheKingsFactorization | Topcoder Archive

Problem Statement

The King of Byteland likes integer factorization. Your task is to help him factor the number N. You will be given the long N and you should return a long[] containing all prime factors of N sorted in non-decreasing order. Note that some primes may occur multiple times in the prime factorization of N. For example, for N = 60 the only correct return value is {2, 2, 3, 5} because 2*2*3*5 = 60.

To make this task easier, the King has decided to give you a hint. He already knows the correct factorization and he will tell you every second number in the correct return value. More precisely, in addition to N you will be given a long[] primes. The number of elements in primes will be (M+1)/2, rounded down, where M is the number of elements in the correct return value. For each valid i, primes[i] will be equal to the element 2i of the correct return value. (All indices are 0-based.)

Given N and primes, return the long[] containing the factorization of N.

Definition

Class:: TheKingsFactorization
Method:: getVector
Parameters:: long, long[]
Returns:: long[]
Method signature:: long[] getVector(long N, long[] primes)
(be sure your method is public)

Constraints

N will be between 2 and 1,000,000,000,000,000,000 (10^18), inclusive.
primes will contain the correct prime factors (as defined in the problem statement).

Examples

```
12
```
```
{2, 3}
```
```
Returns: {2, 2, 3 }
```
```
7
```
```
{7}
```
```
Returns: {7 }
```

{2, 3, 7}

Returns: {2, 2, 3, 3, 7, 7 }

```
49
```
```
{7}
```
```
Returns: {7, 7 }
```
```
210
```
```
{2, 5}
```
```
Returns: {2, 3, 5, 7 }
```

{2, 2, 2, 5, 5}

Returns: {2, 2, 2, 2, 2, 5, 5, 5, 5, 5 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.