Statistics

Problem Statement for "PrimeContainers"

Problem Statement

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

Elly loves "div 2" problems! By this she means problems in which she has to divide by two! She notices that some numbers contain prime numbers in themselves! A number X contains another number Y if Y = X / 2k (here and everywhere later in the statement the results of all divisions are rounded down, i.e., integer divisions), for some non-negative integer k.

She calls all positive integers "prime containers" and defines the size of a prime container as the number of prime numbers contained in that positive integer. For example the size of number 7 is 2, because 7/1 = 7 and 7/2 = 3 are prime; the size of 47 is 5, because 47, 23, 11, 5 and 2 are prime; the size of 959 is 6, since it contains the prime numbers 479, 239, 59, 29, 7 and 3.

Given a positive int N help Elleonora by finding the number of prime numbers it contains.

Definition

Class:
PrimeContainers
Method:
containerSize
Parameters:
int
Returns:
int
Method signature:
int containerSize(int N)
(be sure your method is public)

Notes

  • A prime number is a natural number greater than one that has exactly two distinct natural number divisors: 1 and itself.

Constraints

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

Examples

  1. 10

    Returns: 2

    The generated sequence is 10, 5, 2, 1. Ten is not a prime, however five and two are.

  2. 42

    Returns: 2

    The Answer to Life, The Universe and Everything is quite poor prime container.

  3. 47

    Returns: 5

    One of the examples in the problem statement.

  4. 959

    Returns: 6

    Another example from the problem statement.

  5. 421337

    Returns: 2

  6. 1

    Returns: 0

  7. 10

    Returns: 2

  8. 100

    Returns: 1

  9. 1000

    Returns: 3

  10. 10000

    Returns: 2

  11. 100000

    Returns: 2

  12. 1000000

    Returns: 3

  13. 666

    Returns: 4

  14. 1337

    Returns: 5

  15. 7

    Returns: 2

  16. 23

    Returns: 4

  17. 2879

    Returns: 9

  18. 2

    Returns: 1

  19. 3

    Returns: 1

  20. 11

    Returns: 3

  21. 111111

    Returns: 2

  22. 222222

    Returns: 2

  23. 333333

    Returns: 2

  24. 444444

    Returns: 2

  25. 555555

    Returns: 3

  26. 666666

    Returns: 2

  27. 777777

    Returns: 7

  28. 888888

    Returns: 2

  29. 999999

    Returns: 4

  30. 16

    Returns: 1

  31. 131072

    Returns: 1

  32. 524287

    Returns: 7

  33. 13

    Returns: 2

  34. 50

    Returns: 1

  35. 70

    Returns: 2

  36. 78

    Returns: 2

  37. 313

    Returns: 3

  38. 313131

    Returns: 3

  39. 424242

    Returns: 3

  40. 997

    Returns: 4

  41. 994009

    Returns: 2

  42. 15015

    Returns: 4

  43. 11519

    Returns: 10

  44. 23039

    Returns: 11

  45. 368633

    Returns: 12

  46. 982559

    Returns: 11

  47. 737279

    Returns: 12

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: