JOIN
Get Time

   Problem Statement  

 Problem Statement for TheKingsFactorization

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

0)
    
12
{2, 3}
Returns: {2, 2, 3 }
1)
    
7
{7}
Returns: {7 }
2)
    
1764
{2, 3, 7}
Returns: {2, 2, 3, 3, 7, 7 }
3)
    
49
{7}
Returns: {7, 7 }
4)
    
210
{2, 5}
Returns: {2, 3, 5, 7 }
5)
    
100000
{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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 643 Round 1 - Division I, Level One
       Single Round Match 643 Round 1 - Division II, Level Two