Statistics

Problem Statement for "MagicDiamonds"

Problem Statement

You found n Magic Diamonds in the mountain. You are now thinking about transfering them to your home. The only way you can transfer Magic Diamonds is to use Transfer Magic one or more times.

The Magic Diamonds are very strange. For any positive integer x you can use Transfer Magic to transfer x Magic Diamonds at once. However, if x is a prime number, the Magic Diamonds will disappear instead of getting transferred. You are not allowed to lose any of the Magic Diamonds, therefore you may never use Transfer Magic on a prime number of Magic Diamonds. Your task is to transfer all Magic Diamonds using Transfer Magic as few times as possible.

You are given a long n. Return the minimal number of Transfer Magic usages you need to transfer n Magic Diamonds.

Definition

Class:
MagicDiamonds
Method:
minimalTransfer
Parameters:
long
Returns:
long
Method signature:
long minimalTransfer(long n)
(be sure your method is public)

Notes

  • A positive integer x is a prime number if and only if it has exactly 2 divisors: 1 and x. Note that 1 is not a prime number.
  • Your task can always be accomplished. For example, you can use Transfer Magic n times and transfer 1 Magic Diamond each time.

Constraints

  • n will be between 1 and 1,000,000,000,000 (10^12), inclusive.

Examples

  1. 2

    Returns: 2

    We have to use Transfer Magic twice, each time we transfer 1 Magic Diamond.

  2. 4294967297

    Returns: 1

    We just need to use Transfer Magic once, because 4294967297 is not a prime. We have 4294967297 = 641 * 6700417.

  3. 2147483647

    Returns: 2

    This time n is a prime, so we have to use Transfer Magic at least twice. We have 2147483647 = 2147400000 + 83647 (83647 = 233 * 359, which is not a prime), thus the answer is 2.

  4. 1

    Returns: 1

  5. 8566

    Returns: 1

  6. 6308

    Returns: 1

  7. 4081

    Returns: 1

  8. 5680

    Returns: 1

  9. 4427

    Returns: 1

  10. 2739

    Returns: 1

  11. 6181

    Returns: 1

  12. 6274

    Returns: 1

  13. 3601

    Returns: 1

  14. 7506

    Returns: 1

  15. 8951

    Returns: 2

  16. 5345

    Returns: 1

  17. 9621

    Returns: 1

  18. 9300

    Returns: 1

  19. 23

    Returns: 2

  20. 720

    Returns: 1

  21. 2151

    Returns: 1

  22. 7854

    Returns: 1

  23. 3607

    Returns: 2

  24. 1881

    Returns: 1

  25. 6076

    Returns: 1

  26. 9369

    Returns: 1

  27. 3853

    Returns: 2

  28. 8229

    Returns: 1

  29. 205

    Returns: 1

  30. 980

    Returns: 1

  31. 4197

    Returns: 1

  32. 1460

    Returns: 1

  33. 320020303

    Returns: 2

  34. 1021932001

    Returns: 1

  35. 1804873438

    Returns: 1

  36. 625102087

    Returns: 1

  37. 298989654

    Returns: 1

  38. 713692516

    Returns: 1

  39. 2019257625

    Returns: 1

  40. 1567124116

    Returns: 1

  41. 196044214

    Returns: 1

  42. 436143805

    Returns: 1

  43. 1906602942

    Returns: 1

  44. 1651588877

    Returns: 1

  45. 1477002708

    Returns: 1

  46. 1117874276

    Returns: 1

  47. 378147332

    Returns: 1

  48. 557741133

    Returns: 1

  49. 668154454

    Returns: 1

  50. 570251827

    Returns: 1

  51. 1039736738

    Returns: 1

  52. 2099585234

    Returns: 1

  53. 1981093541

    Returns: 1

  54. 1884363755

    Returns: 1

  55. 1865560917

    Returns: 1

  56. 745615932

    Returns: 1

  57. 1214865010

    Returns: 1

  58. 1695760303

    Returns: 1

  59. 1246390622

    Returns: 1

  60. 1692493778

    Returns: 1

  61. 1065227310

    Returns: 1

  62. 1265265799

    Returns: 1

  63. 1084963329

    Returns: 1

  64. 1478843645

    Returns: 1

  65. 2006456208

    Returns: 1

  66. 1722953950

    Returns: 1

  67. 496132103

    Returns: 1

  68. 6562762

    Returns: 1

  69. 957223956

    Returns: 1

  70. 654140677

    Returns: 1

  71. 1586450237

    Returns: 1

  72. 1018720108

    Returns: 1

  73. 2026536822

    Returns: 1

  74. 764222894

    Returns: 1

  75. 1544043251

    Returns: 1

  76. 1034964664

    Returns: 1

  77. 684533819

    Returns: 1

  78. 559623793

    Returns: 2

  79. 1102523518

    Returns: 1

  80. 1103984296

    Returns: 1

  81. 1487426600

    Returns: 1

  82. 1402158154

    Returns: 1

  83. 1000000000000

    Returns: 1

  84. 3

    Returns: 3

  85. 1

    Returns: 1

  86. 4

    Returns: 1

  87. 5

    Returns: 2

  88. 6

    Returns: 1

  89. 7

    Returns: 2

  90. 8

    Returns: 1

  91. 9

    Returns: 1

  92. 10

    Returns: 1

  93. 1000000000000

    Returns: 1

  94. 999999999997

    Returns: 1

  95. 999999999989

    Returns: 2

  96. 22222223

    Returns: 2

  97. 524524524524

    Returns: 1

  98. 524524524521

    Returns: 2

  99. 51432121451

    Returns: 2

  100. 25

    Returns: 1

  101. 11

    Returns: 2

  102. 999999000001

    Returns: 2

  103. 66

    Returns: 1

  104. 16

    Returns: 1

  105. 49

    Returns: 1

  106. 100000000019

    Returns: 2

  107. 982451653

    Returns: 2

  108. 31

    Returns: 2

  109. 424248523252

    Returns: 1

  110. 27

    Returns: 1

  111. 999966000289

    Returns: 1

  112. 10010602793

    Returns: 1

  113. 97969

    Returns: 1

  114. 1000000000

    Returns: 1

  115. 13

    Returns: 2

  116. 1000000007

    Returns: 2

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: