Statistics

Problem Statement for "SmoothDivisors"

Problem Statement

This problem has a time limit of 4 seconds. The memory limit is standard: 256 MB.


A set of integers is called smooth if it can be arranged into a cyclic sequence such that no pair of adjacent elements is coprime. (See Notes for a definition of "coprime".)

(An empty sequence has no pairs of adjacent elements. In a one-element sequence the only element is considered to be its own neighbor and therefore there is one pair of adjacent elements.)


Examples:

  • The set {1, 2, 3, 4, 5} is not smooth because in any cyclic sequence the number 1 has to have two neighbors and it will be coprime with each of them, regardless of what they are.
  • The set {2, 4, 6, 8, 10} is smooth: in fact, any cyclic sequence of these elements works as each two of them have a common factor that is at least 2.
  • The set {2, 4, 27, 54, 666} is smooth: e.g., the cyclic sequence 4, 2, 666, 27, 54 has the desired property.
  • The set {2, 5, 10000} is not smooth. In particular, the sequence 2, 10000, 5 does not work - remember that the sequence is cyclic and therefore 2 and 5 must also have a common factor that is greater than 1.
  • The empty set is smooth, with the empty sequence as a witness.
  • The set {1} is not smooth.
  • The set {42} is smooth.

Proper divisors of a positive integer X are positive integers that divide X and lie strictly between 1 and X itself. For example, 1 and 47 each have no proper divisors, and 14 has two proper divisors: 2 and 7.

A number is called smooth if the set of its proper divisors is smooth.


You are given two integers A and B. Count all smooth integers in the closed range [A, B].

Definition

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

Notes

  • Positive integers X and Y are called coprime if their greatest common divisor is 1.

Constraints

  • 1 <= A <= B <= 40,000,000.

Examples

  1. 213

    219

    Returns: 1

    The only smooth number in this range is 216.

  2. 47

    49

    Returns: 3

    All three numbers in this range are smooth. The set of proper divisors of 47 is {}, the set of proper divisors of 48 is { 2, 3, 4, 6, 8, 12, 16, 24 }, and the set of proper divisors of 49 is { 7 }.

  3. 1

    40000000

    Returns: 31501134

  4. 1

    5

    Returns: 5

    Again, all five numbers in this range are smooth.

  5. 34000046

    34000046

    Returns: 0

    This number is not smooth.

  6. 4195994

    23612003

    Returns: 15270607

  7. 30445337

    37154157

    Returns: 5334720

  8. 17275693

    34389560

    Returns: 13568219

  9. 2745338

    26334552

    Returns: 18551240

  10. 4323

    6875696

    Returns: 5290454

  11. 5171

    36687596

    Returns: 28859198

  12. 28702423

    38088858

    Returns: 7463295

  13. 15954585

    35116029

    Returns: 15188251

  14. 9191

    29676949

    Returns: 23282427

  15. 23719801

    25109938

    Returns: 1101848

  16. 37432683

    38594514

    Returns: 925347

  17. 2367529

    16013463

    Returns: 10676744

  18. 6573117

    22409534

    Returns: 12468216

  19. 25741531

    38812550

    Returns: 10389593

  20. 6516181

    15230880

    Returns: 6840389

  21. 6827

    31610304

    Returns: 24820358

  22. 19214497

    23692719

    Returns: 3543817

  23. 17554987

    37263273

    Returns: 15633775

  24. 7929

    37942258

    Returns: 29856157

  25. 20951834

    37764719

    Returns: 13348512

  26. 17464663

    34856282

    Returns: 13789719

  27. 7646094

    13897326

    Returns: 4907060

  28. 16987852

    32574562

    Returns: 12352440

  29. 1019398

    29788710

    Returns: 22616149

  30. 4355

    36708054

    Returns: 28876012

  31. 34308390

    36699459

    Returns: 1902207

  32. 9959

    29233489

    Returns: 22929595

  33. 17784751

    34693030

    Returns: 13407143

  34. 1492058

    21138827

    Returns: 15397940

  35. 14184447

    23217275

    Returns: 7136622

  36. 11856622

    12349106

    Returns: 387280

  37. 2240

    13332952

    Returns: 10356506

  38. 23089143

    38226635

    Returns: 12024490

  39. 7253472

    17909019

    Returns: 8377898

  40. 30327

    8212502

    Returns: 6317369

  41. 4330

    24779853

    Returns: 19400522

  42. 2798790

    9424663

    Returns: 5162072

  43. 32949329

    34336791

    Returns: 1102970

  44. 33198408

    35451928

    Returns: 1791786

  45. 1210

    38073342

    Returns: 29965072

  46. 10104395

    11752257

    Returns: 1294315

  47. 6206

    15737114

    Returns: 12248033

  48. 4960

    8264322

    Returns: 6375591

  49. 3616633

    36765974

    Returns: 26167115

  50. 16046935

    35895681

    Returns: 15735843

  51. 36905061

    38906925

    Returns: 1594588

  52. 5415898

    38308069

    Returns: 25997734

  53. 1878

    37347542

    Returns: 29386629

  54. 27748030

    28027736

    Returns: 222050

  55. 20321389

    37870933

    Returns: 13931668

  56. 1

    3987654

    Returns: 3045392

  57. 1

    39999942

    Returns: 31501086

  58. 12

    12

    Returns: 0

  59. 85

    40000000

    Returns: 31501085

  60. 18

    18

    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: