Statistics

Problem Statement for "DivisorInc"

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

  1. 4

    24

    Returns: 5

    The example from the problem statement.

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

  3. 486

    7128

    Returns: 9

    The shortest order of operations is: 486->729->972->1458->2187->2916->4374->6561->6804->7128

  4. 8748

    83462

    Returns: 10

    The shortest order of operations is: 8748->13122->19683->26244->39366->59049->78732->83106->83448->83460->83462.

  5. 235

    98234

    Returns: 21

  6. 4

    99991

    Returns: -1

    The number 99991 can't be obtained because it is prime.

  7. 82736

    82736

    Returns: 0

    We don't need any operations. N and M are already equal.

  8. 4

    85678

    Returns: 33

  9. 6

    85678

    Returns: 32

  10. 8

    85678

    Returns: 31

  11. 9

    85678

    Returns: 31

  12. 10

    80998

    Returns: 30

  13. 12

    85678

    Returns: 30

  14. 14

    95014

    Returns: 30

  15. 100000

    100000

    Returns: 0

  16. 99991

    99991

    Returns: 0

  17. 99990

    99991

    Returns: -1

  18. 4

    99991

    Returns: -1

  19. 99991

    100000

    Returns: -1

  20. 89989

    89989

    Returns: 0

  21. 5

    5

    Returns: 0

  22. 5

    100000

    Returns: -1

  23. 4

    4

    Returns: 0

  24. 4

    5

    Returns: -1

  25. 4

    6

    Returns: 1

  26. 5

    5

    Returns: 0

  27. 5

    6

    Returns: -1

  28. 8

    9

    Returns: -1

  29. 15

    16

    Returns: -1

  30. 25

    27

    Returns: -1

  31. 78961

    79523

    Returns: 2

  32. 152

    72414

    Returns: 19

  33. 815

    79512

    Returns: 16

  34. 648

    70736

    Returns: 16

  35. 67

    89772

    Returns: -1

  36. 619

    64841

    Returns: -1

  37. 944

    60436

    Returns: 14

  38. 671

    54007

    Returns: 17

  39. 978

    90057

    Returns: 16

  40. 676

    12948

    Returns: 10

  41. 659

    78938

    Returns: -1

  42. 244

    38771

    Returns: 18

  43. 588

    77323

    Returns: -1

  44. 407

    23013

    Returns: 14

  45. 587

    40920

    Returns: -1

  46. 62

    78505

    Returns: 23

  47. 928

    18081

    Returns: 10

  48. 163

    6435

    Returns: -1

  49. 582

    39983

    Returns: -1

  50. 321

    54237

    Returns: 17

  51. 583

    74629

    Returns: 18

  52. 551

    75833

    Returns: -1

  53. 484

    61330

    Returns: 16

  54. 344

    67443

    Returns: 18

  55. 408

    84496

    Returns: 18

  56. 553

    34526

    Returns: 15

  57. 63

    39365

    Returns: 21

  58. 493

    27322

    Returns: 15

  59. 234

    20540

    Returns: 14

  60. 59

    99723

    Returns: -1

  61. 985

    53537

    Returns: 14

  62. 958

    41354

    Returns: 14

  63. 484

    12287

    Returns: 11

  64. 955

    6858

    Returns: 8

  65. 937

    18296

    Returns: -1

  66. 390

    5398

    Returns: 11

  67. 621

    29408

    Returns: 14

  68. 447

    1105

    Returns: 5

  69. 782

    77551

    Returns: -1

  70. 497

    47853

    Returns: 15

  71. 634

    71427

    Returns: 16

  72. 2697

    96219

    Returns: 14

  73. 4834

    55889

    Returns: -1

  74. 9086

    76594

    Returns: 9

  75. 6113

    57516

    Returns: -1

  76. 2309

    38189

    Returns: -1

  77. 388

    78967

    Returns: 17

  78. 9897

    28646

    Returns: 7

  79. 6000

    67194

    Returns: 10

  80. 6297

    66816

    Returns: 10

  81. 2915

    40460

    Returns: 10

  82. 1262

    85473

    Returns: 15

  83. 967

    16670

    Returns: -1

  84. 5326

    60485

    Returns: 10

  85. 9705

    74714

    Returns: 10

  86. 4766

    83721

    Returns: 11

  87. 1981

    11997

    Returns: 8

  88. 2609

    28706

    Returns: -1

  89. 2523

    85084

    Returns: 14

  90. 6733

    75639

    Returns: -1

  91. 4246

    10673

    Returns: 6

  92. 4063

    73030

    Returns: 11

  93. 3555

    17535

    Returns: 7

  94. 7534

    84590

    Returns: 11

  95. 7742

    61206

    Returns: 9

  96. 4328

    21101

    Returns: -1

  97. 3103

    20826

    Returns: 9

  98. 719

    49584

    Returns: -1

  99. 7686

    24779

    Returns: 6

  100. 7898

    12485

    Returns: 4

  101. 465

    82543

    Returns: 18

  102. 6757

    80471

    Returns: -1

  103. 5879

    90191

    Returns: -1

  104. 9213

    25637

    Returns: 7

  105. 7340

    32633

    Returns: -1

  106. 7220

    45460

    Returns: 8

  107. 828

    13374

    Returns: 10

  108. 951

    16013

    Returns: 12

  109. 3863

    61573

    Returns: -1

  110. 769

    87386

    Returns: -1

  111. 8835

    61347

    Returns: 8

  112. 90447

    99886

    Returns: 6

  113. 43397

    61548

    Returns: -1

  114. 84573

    89908

    Returns: 4

  115. 97173

    99242

    Returns: 4

  116. 31068

    69281

    Returns: 7

  117. 12017

    74874

    Returns: 9

  118. 51492

    52076

    Returns: 3

  119. 38083

    55729

    Returns: -1

  120. 72501

    79087

    Returns: -1

  121. 97816

    98562

    Returns: 4

  122. 25406

    70697

    Returns: 7

  123. 84901

    93979

    Returns: -1

  124. 78617

    91788

    Returns: 4

  125. 56971

    59329

    Returns: 5

  126. 12248

    73917

    Returns: 8

  127. 18875

    35155

    Returns: 5

  128. 35294

    79769

    Returns: -1

  129. 44861

    52808

    Returns: 3

  130. 52704

    90705

    Returns: 6

  131. 5347

    22614

    Returns: -1

  132. 125

    89989

    Returns: -1

  133. 4

    576

    Returns: 14

  134. 235

    98266

    Returns: 20

  135. 4

    10000

    Returns: 23

  136. 8

    83462

    Returns: 29

  137. 235

    98234

    Returns: 21

  138. 8748

    83462

    Returns: 10

  139. 27

    97234

    Returns: 26

  140. 655

    99991

    Returns: -1

  141. 6

    99899

    Returns: 31

  142. 4

    65536

    Returns: 28

  143. 4

    24

    Returns: 5

  144. 4

    100000

    Returns: 30

  145. 1245

    99991

    Returns: -1

  146. 4

    99982

    Returns: 31

  147. 120

    98444

    Returns: 20

  148. 4

    99999

    Returns: 30

  149. 128

    243

    Returns: 3

  150. 17

    17

    Returns: 0

  151. 98

    100

    Returns: 1

  152. 4

    5

    Returns: -1

  153. 800

    801

    Returns: -1

  154. 9

    100000

    Returns: 28

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: