Statistics

Problem Statement for "SquareFreeNumbers"

Problem Statement

A number is called square-free if it is not divisible by a perfect square which is greater than one. A perfect square is the square of an integer. Return the number of square-free numbers between min and max, inclusive.

Definition

Class:
SquareFreeNumbers
Method:
getCount
Parameters:
long, long
Returns:
int
Method signature:
int getCount(long min, long max)
(be sure your method is public)

Constraints

  • min will be between 1 and 1,000,000,000,000, inclusive.
  • max will be between min and (min + 1,000,000), inclusive.

Examples

  1. 1

    10

    Returns: 7

    Numbers 4, 8 and 9 are not square-free.

  2. 15

    15

    Returns: 1

    min and max can be equal.

  3. 1

    1000

    Returns: 608

  4. 1

    1000001

    Returns: 607927

  5. 123456

    234567

    Returns: 67553

  6. 99999900000

    100000000000

    Returns: 60799

  7. 999999000000

    1000000000000

    Returns: 607923

  8. 1000000000000

    1000001000000

    Returns: 607940

  9. 3561

    3585

    Returns: 15

  10. 3819

    3831

    Returns: 8

  11. 1299

    1299

    Returns: 1

  12. 2178

    2190

    Returns: 8

  13. 6783

    6833

    Returns: 31

  14. 4979

    4999

    Returns: 13

  15. 9421

    9430

    Returns: 6

  16. 3699

    3715

    Returns: 11

  17. 5638

    5656

    Returns: 12

  18. 452

    546

    Returns: 58

  19. 543799478938

    543799920081

    Returns: 268169

  20. 738297687942

    738298114842

    Returns: 259534

  21. 725266112424

    725266282081

    Returns: 103141

  22. 420737591142

    420738110028

    Returns: 315455

  23. 327185268854

    327185368189

    Returns: 60387

  24. 290431986172

    290432637025

    Returns: 395658

  25. 699770747199

    699770961193

    Returns: 130106

  26. 707061385464

    707062211618

    Returns: 502208

  27. 405742321980

    405742726464

    Returns: 245890

  28. 776928823128

    776929266670

    Returns: 269661

  29. 947825892522

    947826283177

    Returns: 237481

  30. 861444347736

    861445082669

    Returns: 446802

  31. 353769998293

    353770484935

    Returns: 295827

  32. 785540533611

    785541183384

    Returns: 395010

  33. 176526874135

    176527666909

    Returns: 481972

  34. 874798576806

    874799006922

    Returns: 261493

  35. 117945762779

    117946587149

    Returns: 501152

  36. 381852861479

    381853582417

    Returns: 438276

  37. 867064911598

    867065382335

    Returns: 286188

  38. 27257040331

    27257084501

    Returns: 26848

  39. 453034187638

    453034216792

    Returns: 17719

  40. 949208917364

    949209279896

    Returns: 220403

  41. 17985075368

    17985241694

    Returns: 101110

  42. 828033060601

    828033869971

    Returns: 492036

  43. 798103975354

    798104501987

    Returns: 320132

  44. 546135370920

    546135418733

    Returns: 29057

  45. 808846352060

    808847138520

    Returns: 478128

  46. 281176345296

    281176963877

    Returns: 376049

  47. 553414255273

    553414852480

    Returns: 363048

  48. 223418277961

    223419226100

    Returns: 576406

  49. 320192675619

    320192814300

    Returns: 84303

  50. 240365852133

    240366300098

    Returns: 272325

  51. 328533158922

    328533934779

    Returns: 471658

  52. 129856746681

    129856939870

    Returns: 117433

  53. 82226161988

    82226645412

    Returns: 293894

  54. 538500012536

    538500231220

    Returns: 132937

  55. 658481874286

    658482838656

    Returns: 586260

  56. 526229719217

    526230595201

    Returns: 532521

  57. 281902672774

    281902888837

    Returns: 131339

  58. 502810227780

    502810614750

    Returns: 235240

  59. 777471333152

    777471422358

    Returns: 54219

  60. 198711428081

    198711444038

    Returns: 9699

  61. 12410453499

    12410685737

    Returns: 141183

  62. 957453761132

    957454647086

    Returns: 538597

  63. 791097591353

    791097812178

    Returns: 134253

  64. 869511363032

    869511897631

    Returns: 324994

  65. 926726930333

    926727193096

    Returns: 159757

  66. 836174322976

    836174893495

    Returns: 346846

  67. 342318838674

    342319301719

    Returns: 281480

  68. 815203381781

    815204084666

    Returns: 427301

  69. 870152282000

    870153282000

    Returns: 607947

  70. 734561983058

    734562983058

    Returns: 607924

  71. 862402441509

    862403441509

    Returns: 607941

  72. 227753004967

    227754004967

    Returns: 607909

  73. 708436660844

    708437660844

    Returns: 607917

  74. 437880708831

    437881708831

    Returns: 607916

  75. 532877585920

    532878585920

    Returns: 607924

  76. 955001376644

    955002376644

    Returns: 607922

  77. 739043547498

    739044547498

    Returns: 607922

  78. 20712929577

    20713929577

    Returns: 607917

  79. 741581683401

    741582683401

    Returns: 607921

  80. 555887255367

    555888255367

    Returns: 607906

  81. 861078731312

    861079731312

    Returns: 607918

  82. 167300488955

    167301488955

    Returns: 607928

  83. 56596581099

    56597581099

    Returns: 607934

  84. 999966000289

    999967000289

    Returns: 607924

  85. 999999999990

    1000000999990

    Returns: 607941

  86. 1000000000000

    1000000000000

    Returns: 0

  87. 900000000000

    900001000000

    Returns: 607949

  88. 999999999999

    1000000999999

    Returns: 607940

  89. 999999900001

    1000000000000

    Returns: 60799

  90. 264431464400

    264432464400

    Returns: 607930

  91. 1000000000000

    1000000100000

    Returns: 60788

  92. 1

    1000000

    Returns: 607926

  93. 998998998998

    998999998998

    Returns: 607918

  94. 900000000000

    900000100000

    Returns: 60791

  95. 93642413787

    93643413787

    Returns: 607934

  96. 979611001009

    979612001003

    Returns: 607915

  97. 58227239070

    58227339070

    Returns: 60795

  98. 999999000001

    1000000000000

    Returns: 607923

  99. 999999999997

    1000000999996

    Returns: 607940

  100. 326918592000

    326919592000

    Returns: 607903

  101. 999348435789

    999349435789

    Returns: 607924

  102. 100000000000

    100001000000

    Returns: 607894

  103. 999999000100

    1000000000000

    Returns: 607864

  104. 1000000

    2000000

    Returns: 607951

  105. 999000000000

    999000999999

    Returns: 607937

  106. 999998999999

    999999999999

    Returns: 607924

  107. 999999000000

    999999999999

    Returns: 607923

  108. 999998000000

    999999000000

    Returns: 607935

  109. 64

    64

    Returns: 0

  110. 1000000000000

    1000000999999

    Returns: 607940

  111. 1000000000000

    1000000973389

    Returns: 591765

  112. 999998990981

    999999990981

    Returns: 607922

  113. 1000000000

    1000999999

    Returns: 607938

  114. 1000000000

    1001000000

    Returns: 607938

  115. 90009000000

    90010000000

    Returns: 607926

  116. 1000000000000

    1000000590000

    Returns: 358672

  117. 10000000000

    10001000000

    Returns: 607921

  118. 12

    16

    Returns: 3

  119. 4

    1000

    Returns: 605

  120. 9

    9

    Returns: 0

  121. 1159438408

    1160149421

    Returns: 432220

  122. 8

    8

    Returns: 0

  123. 999998159037

    999999159037

    Returns: 607935

  124. 1000000000

    1000999991

    Returns: 607933

  125. 400000000000

    400001000000

    Returns: 607936

  126. 57000000993

    57001000991

    Returns: 607921

  127. 100000000000

    100000100000

    Returns: 60782

  128. 10000

    11000

    Returns: 604

  129. 999999988999

    999999999999

    Returns: 6691

  130. 999900

    1000000

    Returns: 58

  131. 100007

    100007

    Returns: 1

  132. 999965900289

    999966900289

    Returns: 607924

  133. 999999900000

    1000000000000

    Returns: 60799

  134. 4

    4

    Returns: 0

  135. 40001200009

    40002200009

    Returns: 607927

  136. 40001200009

    40001200009

    Returns: 0

  137. 30

    50

    Returns: 13

  138. 4

    5

    Returns: 1

  139. 1

    4

    Returns: 3

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: