Statistics

Problem Statement for "Underprimes"

Problem Statement

The prime factorization of a number X is the list of prime numbers that multiply together to form X. For example, the prime factorization of 12 is 2 * 2 * 3. Note that 1 is not a prime number.

An underprime is a number whose prime factorization contains a prime number of elements. For example, 12 is an underprime because its prime factorization contains 3 elements, and 3 is a prime number. Given ints A and B, return the number of underprimes between A and B, inclusive.

Definition

Class:
Underprimes
Method:
howMany
Parameters:
int, int
Returns:
int
Method signature:
int howMany(int A, int B)
(be sure your method is public)

Notes

  • A positive integer number is called prime if it has exactly two divisors - 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, and 4, 6, 8 and 9 are not prime. By convention, 1 is not considered to be a prime number.
  • All prime factorizations of the same integer always contain the same prime numbers and can only differ by the order of primes within them.

Constraints

  • A will be between 2 and 100000, inclusive.
  • B will be between A and 100000, inclusive.

Examples

  1. 2

    10

    Returns: 5

    The underprimes in this interval are: 4, 6, 8, 9, 10.

  2. 100

    105

    Returns: 2

    The underprimes in this interval are 102 = 2 * 3 * 17 and 105 = 3 * 5 * 7.

  3. 17

    17

    Returns: 0

    17 is a prime number, so its prime factorization contains one element. 1 is not a prime, so 17 is not an underprime.

  4. 312

    12839

    Returns: 7987

  5. 123

    456

    Returns: 217

  6. 12345

    12345

    Returns: 1

  7. 2

    100000

    Returns: 63255

  8. 127

    129

    Returns: 2

  9. 162

    32918

    Returns: 20824

  10. 2

    99999

    Returns: 63255

  11. 11

    99998

    Returns: 63250

  12. 111

    99997

    Returns: 63189

  13. 12345

    12345

    Returns: 1

  14. 11

    13

    Returns: 1

  15. 228

    23094

    Returns: 14563

  16. 29

    2309

    Returns: 1456

  17. 7328

    23409

    Returns: 10228

  18. 2378

    32492

    Returns: 19142

  19. 9832

    98829

    Returns: 56250

  20. 11111

    22222

    Returns: 7045

  21. 11111

    11111

    Returns: 1

  22. 1111

    1111

    Returns: 1

  23. 111

    111

    Returns: 1

  24. 12

    13

    Returns: 1

  25. 47203

    47230

    Returns: 18

  26. 12345

    12346

    Returns: 2

  27. 888

    999

    Returns: 79

  28. 2

    10000

    Returns: 6396

  29. 12

    12

    Returns: 1

  30. 397

    87993

    Returns: 55435

  31. 17

    99013

    Returns: 62642

  32. 3

    99999

    Returns: 63255

  33. 98

    99998

    Returns: 63197

  34. 5

    7000

    Returns: 4486

  35. 12

    99999

    Returns: 63250

  36. 3

    9000

    Returns: 5746

  37. 2

    99997

    Returns: 63254

  38. 3

    100000

    Returns: 63255

  39. 56

    98345

    Returns: 62218

  40. 99999

    100000

    Returns: 0

  41. 10

    10000

    Returns: 6392

  42. 123

    2356

    Returns: 1425

  43. 123

    56798

    Returns: 35958

  44. 5498

    5499

    Returns: 1

  45. 99842

    99842

    Returns: 1

  46. 4

    4

    Returns: 1

  47. 10

    10

    Returns: 1

  48. 2

    98000

    Returns: 62028

  49. 512

    512

    Returns: 0

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: