TopCoder problem "DivisorInc" used in SRM 302 (Division I Level One , Division II Level Three)



Problem Statement

    

There is an integer K. You are allowed to add to K any of its divisors not equal to 1 and K. The same operation can be applied to the resulting number and so on. Notice that starting from the number 4, we can reach any composite number by applying several such operations. For example, the number 24 can be reached starting from 4 using 5 operations: 4->6->8->12->18->24.

You will solve a more general problem. Given ints N and M, return the minimal number of the described operations necessary to transform N into M. Return -1 if M can't be obtained from N.

 

Definition

    
Class:DivisorInc
Method:countOperations
Parameters:int, int
Returns:int
Method signature:int countOperations(int N, int M)
(be sure your method is public)
    
 

Constraints

-N will be between 4 and 100000, inclusive.
-M will be between N and 100000, inclusive.
 

Examples

0)
    
4
24
Returns: 5
The example from the problem statement.
1)
    
4
576
Returns: 14
The shortest order of operations is: 4->6->8->12->18->27->36->54->81->108->162->243->324->432->576.
2)
    
8748
83462
Returns: 10
The shortest order of operations is: 8748->13122->19683->26244->39366->59049->78732->83106->83448->83460->83462.
3)
    
235
98234
Returns: 21
4)
    
4
99991
Returns: -1
The number 99991 can't be obtained because it is prime.
5)
    
82736
82736
Returns: 0
We don't need any operations. N and M are already equal.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9823&pm=6186

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , legakis , Olexiy

Problem categories:

Graph Theory, Math