Statistics

Problem Statement for "AlmostPrime"

Problem Statement

A number is called "almost prime" if it is a power of a prime number, but is not a prime number itself. Note that 1 is not almost prime. You are given two Strings A and B, both representing integers (without leading zeros). Return the number of integers between A and B, inclusive, that are almost prime.

Definition

Class:
AlmostPrime
Method:
count
Parameters:
String, String
Returns:
int
Method signature:
int count(String A, String B)
(be sure your method is public)

Constraints

  • A will represent an integer between 1 and 10^14, inclusive.
  • B will represent an integer between A and 10^14, inclusive.
  • Both A and B will have no leading zeros.

Examples

  1. "1"

    "10"

    Returns: 3

    4, 8 and 9 are almost prime here.

  2. "1"

    "1000"

    Returns: 25

  3. "134"

    "53686423"

    Returns: 1074

  4. "123"

    "346458759636"

    Returns: 49439

  5. "1"

    "100000000000000"

    Returns: 670121

  6. "75746"

    "3464578568"

    Returns: 6236

  7. "123456789123"

    "123456789123"

    Returns: 0

  8. "549755813888"

    "549755813888"

    Returns: 1

  9. "847288609443"

    "847288609443"

    Returns: 1

  10. "847288609443"

    "847288609444"

    Returns: 1

  11. "847288609442"

    "847288609444"

    Returns: 1

  12. "2423"

    "43675485656"

    Returns: 19383

  13. "5254235"

    "43654575"

    Returns: 564

  14. "56376578567"

    "78456464454"

    Returns: 3488

  15. "78697845445"

    "78953453452"

    Returns: 47

  16. "425346457569"

    "458670978097"

    Returns: 1907

  17. "1000"

    "10000000"

    Returns: 530

  18. "214358881"

    "137858491849"

    Returns: 30637

  19. "3404825447"

    "762939453125"

    Returns: 64511

  20. "22164362129"

    "678223072849"

    Returns: 52756

  21. "5324"

    "894739"

    Returns: 183

  22. "831241"

    "21942839423234"

    Returns: 331354

  23. "31"

    "4289348239423"

    Returns: 156158

  24. "70368744177664"

    "70368744177664"

    Returns: 1

  25. "70368744177665"

    "70368744177665"

    Returns: 0

  26. "70368744177663"

    "70368744177663"

    Returns: 0

  27. "35184372088831"

    "35184372088831"

    Returns: 0

  28. "17592186044415"

    "17592186044415"

    Returns: 0

  29. "137438953471"

    "137438953471"

    Returns: 0

  30. "78310985282"

    "23298085122480"

    Returns: 315626

  31. "68630377364884"

    "70368744177663"

    Returns: 6571

  32. "412423"

    "100000000000000"

    Returns: 669946

  33. "1"

    "10000000000000"

    Returns: 230567

  34. "62710560"

    "62710562"

    Returns: 1

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: