Statistics

Problem Statement for "CompositeSmash"

Problem Statement

Toastwoman wants to be a magical girl. As training, she wants to make a ball that contains an integer target.

Initially she has a ball that contains an integer N. She can smash a ball that contains a composite number (see notes for definition) and break it into two balls. Each new ball will also contain an integer. If she smashes a ball that contains a composite number x and it breaks into two balls that contain y and z, it satisfies y &ge 2, z &ge 2 and yz = x. For example, if she smashes a ball that contains 12, it breaks into 2 and 6 or 3 and 4. Toastwoman can control the ball she smashes, but she can't control the numbers in the two new balls when there are multiple pairs of (y, z) that satisfy the above conditions. She can apply the described ball smash operation arbitrary number of times, but she can't smash a ball that contains a non-composite number.

If she can always make a ball that contains target, return "Yes" (quotes for clarity). Otherwise, return "No" (quotes for clarity).

Definition

Class:
CompositeSmash
Method:
thePossible
Parameters:
int, int
Returns:
String
Method signature:
String thePossible(int N, int target)
(be sure your method is public)

Notes

  • A positive integer x is called a composite number if it has at least one divisor other than 1 and x. For example, 4 and 6 are composite numbers, while 1 and 5 are not composite numbers.

Constraints

  • N will be between 2 and 100,000, inclusive.
  • target will be between 2 and 100,000, inclusive.

Examples

  1. 517

    47

    Returns: "Yes"

    If she smashes 517, it breaks into 11 and 47.

  2. 8

    4

    Returns: "Yes"

    If she smashes 8, it breaks into 2 and 4.

  3. 12

    6

    Returns: "No"

    If she smashes 12 and it breaks into 3 and 4, she can't make 6.

  4. 5

    8

    Returns: "No"

  5. 100000

    100000

    Returns: "Yes"

    She already has target.

  6. 5858

    2

    Returns: "Yes"

  7. 81461

    2809

    Returns: "No"

  8. 2

    2

    Returns: "Yes"

  9. 24517

    24517

    Returns: "Yes"

  10. 23868

    23868

    Returns: "Yes"

  11. 27981

    27981

    Returns: "Yes"

  12. 7581

    7

    Returns: "Yes"

  13. 77202

    3

    Returns: "Yes"

  14. 33649

    23

    Returns: "Yes"

  15. 64175

    17

    Returns: "Yes"

  16. 68408

    503

    Returns: "Yes"

  17. 45676

    601

    Returns: "Yes"

  18. 52247

    4019

    Returns: "Yes"

  19. 40648

    5081

    Returns: "Yes"

  20. 65719

    65719

    Returns: "Yes"

  21. 91733

    91733

    Returns: "Yes"

  22. 8

    4

    Returns: "Yes"

  23. 32768

    4

    Returns: "Yes"

  24. 65536

    4

    Returns: "Yes"

  25. 2187

    9

    Returns: "Yes"

  26. 3125

    25

    Returns: "Yes"

  27. 343

    49

    Returns: "Yes"

  28. 14641

    121

    Returns: "Yes"

  29. 2197

    169

    Returns: "Yes"

  30. 4913

    289

    Returns: "Yes"

  31. 6859

    361

    Returns: "Yes"

  32. 12167

    529

    Returns: "Yes"

  33. 24389

    841

    Returns: "Yes"

  34. 29791

    961

    Returns: "Yes"

  35. 50653

    1369

    Returns: "Yes"

  36. 68921

    1681

    Returns: "Yes"

  37. 79507

    1849

    Returns: "Yes"

  38. 24517

    23868

    Returns: "No"

  39. 27981

    32111

    Returns: "No"

  40. 25696

    63304

    Returns: "No"

  41. 39699

    87448

    Returns: "No"

  42. 92401

    11170

    Returns: "No"

  43. 74346

    71633

    Returns: "No"

  44. 92758

    89633

    Returns: "No"

  45. 70147

    23873

    Returns: "No"

  46. 26578

    20233

    Returns: "No"

  47. 79626

    31543

    Returns: "No"

  48. 996

    6

    Returns: "No"

  49. 69780

    10

    Returns: "No"

  50. 66256

    82

    Returns: "No"

  51. 10998

    39

    Returns: "No"

  52. 55760

    656

    Returns: "No"

  53. 58380

    834

    Returns: "No"

  54. 17578

    8789

    Returns: "No"

  55. 38940

    1770

    Returns: "No"

  56. 53524

    26762

    Returns: "No"

  57. 51162

    25581

    Returns: "No"

  58. 16

    8

    Returns: "No"

  59. 65536

    8

    Returns: "No"

  60. 32768

    8

    Returns: "No"

  61. 65536

    256

    Returns: "No"

  62. 65536

    32768

    Returns: "No"

  63. 6561

    2187

    Returns: "No"

  64. 78125

    15625

    Returns: "No"

  65. 16807

    343

    Returns: "No"

  66. 14641

    1331

    Returns: "No"

  67. 28561

    2197

    Returns: "No"

  68. 83521

    4913

    Returns: "No"

  69. 39601

    199

    Returns: "Yes"

  70. 100000

    2

    Returns: "Yes"

  71. 100000

    50000

    Returns: "No"

  72. 100000

    99999

    Returns: "No"

  73. 64

    8

    Returns: "No"

  74. 512

    8

    Returns: "No"

  75. 10000

    100

    Returns: "No"

  76. 243

    9

    Returns: "Yes"

  77. 169

    13

    Returns: "Yes"

  78. 16

    4

    Returns: "Yes"

  79. 64

    4

    Returns: "Yes"

  80. 4

    2

    Returns: "Yes"

  81. 59049

    9

    Returns: "Yes"

  82. 24

    2

    Returns: "Yes"

  83. 256

    4

    Returns: "Yes"

  84. 32

    4

    Returns: "Yes"

  85. 7

    4

    Returns: "No"

  86. 24983

    6

    Returns: "No"

  87. 25

    5

    Returns: "Yes"

  88. 1024

    2

    Returns: "Yes"

  89. 7

    2

    Returns: "No"

  90. 90090

    4

    Returns: "No"

  91. 11

    3

    Returns: "No"

  92. 221

    5

    Returns: "No"

  93. 25

    3

    Returns: "No"

  94. 7

    5

    Returns: "No"

  95. 3

    2

    Returns: "No"

  96. 101

    3

    Returns: "No"

  97. 81

    9

    Returns: "Yes"

  98. 27

    9

    Returns: "Yes"

  99. 14947

    8911

    Returns: "No"

  100. 32

    16

    Returns: "No"

  101. 64

    16

    Returns: "No"

  102. 11

    7

    Returns: "No"

  103. 13

    2

    Returns: "No"

  104. 100000

    3

    Returns: "No"

  105. 16807

    49

    Returns: "Yes"

  106. 30

    5

    Returns: "Yes"

  107. 10000

    5

    Returns: "Yes"

  108. 5

    3

    Returns: "No"

  109. 2

    3

    Returns: "No"

  110. 17

    13

    Returns: "No"

  111. 1024

    4

    Returns: "Yes"

  112. 4

    3

    Returns: "No"

  113. 66

    6

    Returns: "No"

  114. 7

    3

    Returns: "No"

  115. 50

    97

    Returns: "No"

  116. 37

    2

    Returns: "No"

  117. 512

    9

    Returns: "No"

  118. 150

    25

    Returns: "No"

  119. 101

    50

    Returns: "No"

  120. 65536

    2

    Returns: "Yes"

  121. 85085

    11

    Returns: "Yes"

  122. 72361

    269

    Returns: "Yes"

  123. 840

    2

    Returns: "Yes"

  124. 10000

    10000

    Returns: "Yes"

  125. 50

    7

    Returns: "No"

  126. 15

    2

    Returns: "No"

  127. 24

    6

    Returns: "No"

  128. 105

    7

    Returns: "Yes"

  129. 128

    4

    Returns: "Yes"

  130. 36

    9

    Returns: "No"

  131. 30

    6

    Returns: "No"

  132. 5

    2

    Returns: "No"

  133. 18

    3

    Returns: "Yes"

  134. 97

    2

    Returns: "No"

  135. 12

    3

    Returns: "Yes"

  136. 24

    8

    Returns: "No"

  137. 8

    3

    Returns: "No"

  138. 80

    5

    Returns: "Yes"

  139. 16

    2

    Returns: "Yes"

  140. 70345

    7

    Returns: "No"

  141. 7

    7

    Returns: "Yes"

  142. 625

    25

    Returns: "Yes"

  143. 32

    8

    Returns: "No"

  144. 9

    3

    Returns: "Yes"

  145. 7

    6

    Returns: "No"

  146. 4096

    4

    Returns: "Yes"

  147. 100

    5

    Returns: "Yes"

  148. 36

    6

    Returns: "No"

  149. 5

    4

    Returns: "No"

  150. 48

    3

    Returns: "Yes"

  151. 216

    6

    Returns: "No"

  152. 85386

    2

    Returns: "Yes"

  153. 11

    9

    Returns: "No"

  154. 6

    81

    Returns: "No"

  155. 519

    17

    Returns: "No"

  156. 128

    2

    Returns: "Yes"

  157. 96

    2

    Returns: "Yes"

  158. 42

    2

    Returns: "Yes"

  159. 14

    7

    Returns: "Yes"

  160. 24

    4

    Returns: "No"

  161. 17

    6

    Returns: "No"

  162. 81

    27

    Returns: "No"

  163. 36

    2

    Returns: "Yes"

  164. 99760

    10

    Returns: "No"

  165. 9

    2

    Returns: "No"

  166. 49

    7

    Returns: "Yes"

  167. 30

    3

    Returns: "Yes"

  168. 6054

    1009

    Returns: "Yes"

  169. 3402

    3

    Returns: "Yes"

  170. 17

    5

    Returns: "No"

  171. 10

    7

    Returns: "No"

  172. 90090

    6

    Returns: "No"

  173. 96

    3

    Returns: "Yes"

  174. 12

    4

    Returns: "No"

  175. 101

    101

    Returns: "Yes"

  176. 85085

    3

    Returns: "No"

  177. 2

    4

    Returns: "No"

  178. 60

    5

    Returns: "Yes"

  179. 30

    2

    Returns: "Yes"

  180. 60480

    2

    Returns: "Yes"

  181. 256

    2

    Returns: "Yes"

  182. 8

    8

    Returns: "Yes"

  183. 3

    9

    Returns: "No"

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: