Statistics

Problem Statement for "HolyNumbers"

Problem Statement

NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.


In John's country, the main religion is based on holy numbers. The religion claims something silly like "the holy numbers are those that contain only 4s and 7s in their decimal expansion".


John is a heretic. He does believe in holy numbers, but he is convinced that the religion is mistaken in their definition. The holiness of a number simply cannot depend on the base in which it is represented! After a long meditation, John realized that the prime factorization of a number does not depend on the base in which the number is represented. That was the correct way!


Many years later, John's theory was finally ready. A prime p likes the number x if one of the following two conditions is satisfied:

  • The prime p does not divide x.
  • The prime p does divide x, p is less than or equal to maximalPrime, and the highest power of p that divides x is odd. (In other words, there is a positive odd integer k such that pk divides x, and pk+1 does not divide x.)

The number x is considered holy if all primes like it.


You are given a long upTo and the int maximalPrime. Return the count of holy numbers between 1 and upTo, inclusive.

Definition

Class:
HolyNumbers
Method:
count
Parameters:
long, int
Returns:
long
Method signature:
long count(long upTo, int maximalPrime)
(be sure your method is public)

Notes

  • A prime number is a positive integer with exactly 2 positive integer divisors. The first few primes are 2, 3, 5, 7, 11, ...

Constraints

  • upTo is between 1 and 1010, inclusive.
  • maximalPrime is between 1 and 106, inclusive.

Examples

  1. 10

    100

    Returns: 8

    1, 2, 3, 5, 6, 7, 8 and 10 are holy numbers.

  2. 10

    3

    Returns: 5

    5, 7 and 10 are no longer holy.

  3. 10000000000

    1000000

    Returns: 3336332555

  4. 1

    1

    Returns: 1

  5. 2

    2

    Returns: 2

  6. 123

    12

    Returns: 32

  7. 10000000000

    100

    Returns: 1746758

  8. 123

    456

    Returns: 88

  9. 123456789

    12345

    Returns: 25994500

  10. 10000000000

    1

    Returns: 1

  11. 1

    1000000

    Returns: 1

  12. 5241113320

    512431

    Returns: 1668827996

  13. 6746828174

    968291

    Returns: 2320613033

  14. 8399637274

    641448

    Returns: 2653336377

  15. 5221324628

    383675

    Returns: 1581239056

  16. 4864723792

    743649

    Returns: 1656019874

  17. 740878

    6077

    Returns: 279946

  18. 572774

    9198

    Returns: 242951

  19. 251889

    7160

    Returns: 113632

  20. 367905

    5948

    Returns: 152097

  21. 759462

    1352

    Returns: 184730

  22. 359790

    3787

    Returns: 135545

  23. 679180

    2392

    Returns: 205763

  24. 90807

    3981

    Returns: 42037

  25. 901147

    4135

    Returns: 303109

  26. 793177

    6954

    Returns: 305646

  27. 4063067882

    3632

    Returns: 229286987

  28. 146

    171

    Returns: 106

  29. 2

    52775

    Returns: 2

  30. 574415810

    11

    Returns: 1700

  31. 560011

    625552

    Returns: 394518

  32. 1799455

    9

    Returns: 315

  33. 14639

    577

    Returns: 5816

  34. 787

    3

    Returns: 16

  35. 5014

    11842

    Returns: 3540

  36. 50

    2557

    Returns: 36

  37. 24252681

    3279

    Returns: 4098988

  38. 4226

    3

    Returns: 22

  39. 149

    54228

    Returns: 107

  40. 2835404662

    133504

    Returns: 742041902

  41. 5836

    3

    Returns: 23

  42. 55675284

    151831

    Returns: 22686774

  43. 25465

    469

    Returns: 8541

  44. 1481959

    2611

    Returns: 401004

  45. 423246

    30471

    Returns: 224669

  46. 1307008

    3

    Returns: 49

  47. 2120876497

    11

    Returns: 2093

  48. 1531259442

    365

    Returns: 11331396

  49. 6477

    148

    Returns: 1857

  50. 974872

    6

    Returns: 131

  51. 1146835

    11

    Returns: 525

  52. 2524812301

    18

    Returns: 7631

  53. 7

    1398

    Returns: 6

  54. 17657696

    93

    Returns: 107200

  55. 2708044

    789

    Returns: 368224

  56. 979

    24183

    Returns: 691

  57. 464

    2

    Returns: 5

  58. 1169

    9

    Returns: 57

  59. 62020404

    411

    Returns: 1863966

  60. 34

    5272

    Returns: 26

  61. 100204676

    68

    Returns: 118104

  62. 78491

    626239

    Returns: 55305

  63. 7036

    3599

    Returns: 4556

  64. 10

    3885

    Returns: 8

  65. 216

    45

    Returns: 101

  66. 2275879360

    2239

    Returns: 104818111

  67. 478379

    172269

    Returns: 307353

  68. 3

    327

    Returns: 3

  69. 2427747145

    1137

    Returns: 61545737

  70. 147

    130230

    Returns: 106

  71. 1238

    35

    Returns: 256

  72. 57461072

    2

    Returns: 14

  73. 163

    36

    Returns: 74

  74. 15

    589

    Returns: 12

  75. 228673

    87384

    Returns: 146932

  76. 2611634

    28228

    Returns: 1125276

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: