BigFatInteger | Topcoder Archive

Problem Statement

This problem statement contains superscipts that may not display properly outside the applet.

Lun the dog loves very large integers. Her favorite is A^B (A to the power of B).

She has an integer variable X. Initially, the value of X is set to 1. She can perform the following two kinds of operations in any order, any number of times.

Operation 1: choose a prime number p, then multiply X by p.
Operation 2: choose a positive divisor d of the value of X at that point, then multiply X by d.

You are given two ints A and B. Return the minimum number of operations Lun needs to perform in order to obtain X = A^B from the initial state X = 1.

Definition

Class:: BigFatInteger
Method:: minOperations
Parameters:: int, int
Returns:: int
Method signature:: int minOperations(int A, int B)
(be sure your method is public)

Constraints

A will be between 2 and 1,000,000 (106), inclusive.
B will be between 1 and 1,000,000 (106), inclusive.

Examples

```
6
```
```
1
```
```
Returns: 2
```
Here, AB = 61 = 6. Here is one of the optimal sequences of operations: Perform operation 1 by choosing p=2. X is now 1*2 = 2. Perform operation 1 by choosing p=3. X is now 2*3 = 6.
```
162
```
```
1
```
```
Returns: 4
```
One of the optimal sequences of operations: Perform operation 1 by choosing p=3. X is now 1*3 = 3. Perform operation 1 by choosing p=3. X is now 3*3 = 9. Perform operation 2 by choosing d=9. X is now 9*9 = 81. Perform operation 1 by choosing p=2. X is now 81*2 = 162.
```
999983
```
```
9
```
```
Returns: 5
```
Here, A is prime. One of the optimal sequences of operations: Perform operation 1 by choosing p=A. X is now A. Perform operation 1 by choosing p=A. X is now A2. Perform operation 1 by choosing p=A. X is now A3. Perform operation 2 by choosing d=A3. X is now A6. Perform operation 2 by choosing d=A3. X is now A9.
```
360
```
```
8
```
```
Returns: 8
```

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.