Statistics

Problem Statement for "SmoothNumbersHard"

Problem Statement

A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.

Definition

Class:
SmoothNumbersHard
Method:
countSmoothNumbers
Parameters:
int, int
Returns:
int
Method signature:
int countSmoothNumbers(int N, int k)
(be sure your method is public)

Constraints

  • N will be between 1 and 5,000,000, inclusive.
  • k will be between 1 and 1,000, inclusive.

Examples

  1. 10

    3

    Returns: 7

    Of the first ten positive integers, only 5, 7 and 10 have prime factors greater than 3; the rest are 3-smooth.

  2. 10

    4

    Returns: 7

    4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.

  3. 15

    3

    Returns: 8

  4. 5

    20

    Returns: 5

  5. 5000000

    1000

    Returns: 1196525

  6. 1

    1

    Returns: 1

  7. 1

    100

    Returns: 1

  8. 100000

    1

    Returns: 1

  9. 2

    2

    Returns: 2

  10. 99999

    100

    Returns: 17441

  11. 99999

    96

    Returns: 16760

  12. 99999

    97

    Returns: 17441

  13. 96

    97

    Returns: 96

  14. 96

    96

    Returns: 96

  15. 121

    11

    Returns: 61

  16. 168

    13

    Returns: 87

  17. 50

    7

    Returns: 31

  18. 50000

    10

    Returns: 566

  19. 65536

    2

    Returns: 17

  20. 4999990

    1000

    Returns: 1196523

  21. 5000000

    996

    Returns: 1192345

  22. 5000000

    997

    Returns: 1196525

  23. 5000000

    5

    Returns: 682

  24. 950

    1000

    Returns: 950

  25. 123456

    123

    Returns: 23855

  26. 5000

    1

    Returns: 1

  27. 5000000

    731

    Returns: 1015104

  28. 4989898

    1000

    Returns: 1194680

  29. 5000000

    500

    Returns: 816749

  30. 4999999

    600

    Returns: 903642

  31. 5000000

    343

    Returns: 618234

  32. 5000000

    998

    Returns: 1196525

  33. 5000000

    123

    Returns: 241786

  34. 5000000

    999

    Returns: 1196525

  35. 5000000

    1

    Returns: 1

  36. 5000000

    527

    Returns: 842818

  37. 4987654

    987

    Returns: 1185903

  38. 4000000

    33

    Returns: 33073

  39. 5000000

    978

    Returns: 1183920

  40. 5000000

    717

    Returns: 1004649

  41. 4999678

    675

    Returns: 977640

  42. 4888887

    459

    Returns: 756789

  43. 4123654

    123

    Returns: 215681

  44. 4956349

    997

    Returns: 1188530

  45. 5000000

    991

    Returns: 1192345

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: