TopCoder problem "NumericalPerfectionLevel" used in SRM 444 (Division II Level Two)



Problem Statement

    It is a well known fact that of all numbers, the number 4 is the most relevant. Patterns related to the number 4 tend to appear everywhere. For example, the numerical perfection level is closely related to the number 4.



We define the perfection level of a positive integer N as k if N can be expressed as a product of 4 positive integers, each with a perfection level of at least (k-1), and cannot be expressed as a product of 4 positive integers, each with a perfection level greater than (k-1). There is one exception - if it is not possible to express N as a product of 4 positive integers all greater than 1, then the perfection level of N is 0.



Given a long N, return its perfection level.
 

Definition

    
Class:NumericalPerfectionLevel
Method:getLevel
Parameters:long
Returns:int
Method signature:int getLevel(long N)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 10000000000000 (10^13), inclusive.
 

Examples

0)
    
4
Returns: 0
4 cannot be expressed as a product of 4 numbers all greater than 1.
1)
    
144
Returns: 1
144 = 4 x 2 x 3 x 6

The level of 4, 2, 3 and 6 is 0.
2)
    
1152
Returns: 1
One of many possible ways to express 1152 is:

1152 = 144 x 2 x 2 x 2

Although 144's level is 1, the remaining factors are of level 0. There is no way to express 1152 as a product of four level 1 numbers.
3)
    
1679616
Returns: 2
1679616 = 36 x 36 x 36 x 36

36 = 2 x 2 x 3 x 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10457

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13898&pm=10457

Writer:

vexorian

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Math