Statistics

Problem Statement for "BigFatInteger"

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 AB (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 = AB 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

  1. 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.

  2. 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.

  3. 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.

  4. 360

    8

    Returns: 8

  5. 524288

    1000000

    Returns: 26

  6. 65536

    524288

    Returns: 24

  7. 16384

    599186

    Returns: 24

  8. 1024

    838861

    Returns: 25

  9. 379970

    263530

    Returns: 22

  10. 455613

    850419

    Returns: 22

  11. 1854

    452226

    Returns: 23

  12. 754246

    850987

    Returns: 22

  13. 697793

    479254

    Returns: 21

  14. 493081

    441207

    Returns: 21

  15. 887624

    946668

    Returns: 25

  16. 961298

    769572

    Returns: 23

  17. 19682

    306509

    Returns: 22

  18. 445612

    999460

    Returns: 24

  19. 622658

    20132

    Returns: 17

  20. 210482

    880822

    Returns: 24

  21. 797631

    443335

    Returns: 22

  22. 668882

    81002

    Returns: 21

  23. 428445

    270660

    Returns: 23

  24. 710858

    363565

    Returns: 22

  25. 44916

    166469

    Returns: 23

  26. 848879

    804577

    Returns: 21

  27. 841356

    162093

    Returns: 22

  28. 213201

    968049

    Returns: 23

  29. 254707

    965564

    Returns: 22

  30. 686279

    257820

    Returns: 21

  31. 460121

    142942

    Returns: 20

  32. 621718

    603423

    Returns: 23

  33. 185512

    439925

    Returns: 23

  34. 594994

    377489

    Returns: 22

  35. 73092

    588660

    Returns: 24

  36. 737962

    493538

    Returns: 22

  37. 857375

    135794

    Returns: 21

  38. 794031

    507542

    Returns: 22

  39. 935818

    922290

    Returns: 23

  40. 952441

    124485

    Returns: 20

  41. 916856

    264083

    Returns: 23

  42. 289575

    210001

    Returns: 24

  43. 163891

    489461

    Returns: 22

  44. 111953

    312746

    Returns: 20

  45. 900817

    639346

    Returns: 21

  46. 668031

    979819

    Returns: 24

  47. 164082

    554344

    Returns: 25

  48. 435906

    992603

    Returns: 25

  49. 33248

    345993

    Returns: 23

  50. 302982

    226042

    Returns: 21

  51. 515647

    495465

    Returns: 21

  52. 446823

    421924

    Returns: 25

  53. 191011

    523830

    Returns: 21

  54. 226953

    620987

    Returns: 24

  55. 638897

    359602

    Returns: 22

  56. 422949

    565107

    Returns: 22

  57. 795322

    838149

    Returns: 23

  58. 622176

    150605

    Returns: 23

  59. 502320

    325115

    Returns: 27

  60. 446040

    553481

    Returns: 26

  61. 822360

    567775

    Returns: 27

  62. 252420

    775779

    Returns: 26

  63. 590940

    876037

    Returns: 26

  64. 124740

    689286

    Returns: 27

  65. 308280

    841345

    Returns: 27

  66. 994140

    468144

    Returns: 26

  67. 771540

    403026

    Returns: 26

  68. 567420

    246984

    Returns: 24

  69. 937860

    133259

    Returns: 25

  70. 557340

    825067

    Returns: 26

  71. 148260

    76492

    Returns: 23

  72. 338520

    608233

    Returns: 27

  73. 463680

    4674

    Returns: 20

  74. 773640

    834346

    Returns: 27

  75. 97860

    3880

    Returns: 18

  76. 62160

    649464

    Returns: 27

  77. 800100

    751399

    Returns: 26

  78. 499800

    317719

    Returns: 25

  79. 555660

    470053

    Returns: 25

  80. 476280

    741441

    Returns: 26

  81. 569940

    980627

    Returns: 27

  82. 78540

    773600

    Returns: 27

  83. 800520

    944597

    Returns: 27

  84. 161280

    571059

    Returns: 27

  85. 206220

    943239

    Returns: 26

  86. 688380

    70534

    Returns: 24

  87. 418320

    938754

    Returns: 27

  88. 843360

    714263

    Returns: 27

  89. 252000

    119821

    Returns: 24

  90. 68040

    283105

    Returns: 25

  91. 719460

    8065

    Returns: 19

  92. 159180

    679816

    Returns: 26

  93. 333060

    296934

    Returns: 26

  94. 858900

    678889

    Returns: 26

  95. 413700

    102879

    Returns: 23

  96. 744240

    792734

    Returns: 27

  97. 154560

    481290

    Returns: 27

  98. 27300

    407728

    Returns: 25

  99. 96600

    827279

    Returns: 27

  100. 836220

    587346

    Returns: 27

  101. 526260

    83989

    Returns: 23

  102. 541800

    484661

    Returns: 26

  103. 930720

    512980

    Returns: 27

  104. 24360

    357852

    Returns: 26

  105. 899640

    128206

    Returns: 24

  106. 879480

    346627

    Returns: 25

  107. 963480

    533980

    Returns: 27

  108. 414960

    216678

    Returns: 26

  109. 288

    10000

    Returns: 18

  110. 777600

    1000000

    Returns: 26

  111. 32768

    1

    Returns: 5

  112. 32

    3

    Returns: 5

  113. 1000000

    1000000

    Returns: 25

  114. 2

    15

    Returns: 5

  115. 32

    5

    Returns: 6

  116. 2

    255

    Returns: 9

  117. 2

    7

    Returns: 4

  118. 72

    17

    Returns: 8

  119. 216

    5

    Returns: 6

  120. 432000

    24

    Returns: 11

  121. 8

    5

    Returns: 5

  122. 9

    7

    Returns: 5

  123. 210

    254

    Returns: 12

  124. 840

    10

    Returns: 9

  125. 216

    1

    Returns: 4

  126. 265837

    5

    Returns: 6

  127. 737280

    1000000

    Returns: 27

  128. 64

    657

    Returns: 13

  129. 360

    21

    Returns: 9

  130. 216

    12345

    Returns: 18

  131. 8

    21

    Returns: 7

  132. 1440

    5

    Returns: 8

  133. 3

    7

    Returns: 4

  134. 579428

    146145

    Returns: 22

  135. 512

    9

    Returns: 8

  136. 27

    5

    Returns: 5

  137. 2

    31

    Returns: 6

  138. 432

    1

    Returns: 4

  139. 6

    7

    Returns: 5

  140. 32

    6

    Returns: 6

  141. 648

    1

    Returns: 4

  142. 9

    1

    Returns: 2

  143. 67500

    1

    Returns: 5

  144. 315000

    47

    Returns: 12

  145. 40

    5

    Returns: 6

  146. 7

    127

    Returns: 8

  147. 4

    1

    Returns: 2

  148. 2

    1023

    Returns: 11

  149. 900000

    3

    Returns: 7

  150. 170100

    424242

    Returns: 26

  151. 840

    125

    Returns: 13

  152. 52488

    1

    Returns: 5

  153. 2

    27

    Returns: 6

  154. 128

    1

    Returns: 4

  155. 20182

    1

    Returns: 2

  156. 33750

    1

    Returns: 5

  157. 29934

    745159

    Returns: 24

  158. 1536

    9

    Returns: 9

  159. 2048

    11

    Returns: 8

  160. 6912

    1

    Returns: 5

  161. 567808

    334575

    Returns: 24

  162. 6

    859593

    Returns: 22

  163. 80

    59

    Returns: 10

  164. 8

    9

    Returns: 6

  165. 59049

    10

    Returns: 8

  166. 8

    10

    Returns: 6

  167. 279936

    1

    Returns: 5

  168. 131072

    17

    Returns: 10

  169. 399964

    27893

    Returns: 18

  170. 16

    7

    Returns: 6

  171. 2

    63

    Returns: 7

  172. 864

    3

    Returns: 6

  173. 7776

    3

    Returns: 6

  174. 32

    17

    Returns: 8

  175. 2

    127

    Returns: 8

  176. 23328

    1

    Returns: 5

  177. 27

    10

    Returns: 6

  178. 7

    7

    Returns: 4

  179. 559872

    1

    Returns: 5

  180. 478034

    1000000

    Returns: 22

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.
This problem was used for: