Statistics

Problem Statement for "SquareFree"

Problem Statement

A positive integer is said to be squarefree if it is divisible by no perfect square larger than 1. For example, the first few squarefree numbers are {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, ...}. Create a class SquareFree that contains a method getNumber, which is given an int n. The method should return the nth smallest squarefree number. Note this is 1-indexed, so if n = 1, the method should return the smallest squarefree number.

Definition

Class:
SquareFree
Method:
getNumber
Parameters:
int
Returns:
int
Method signature:
int getNumber(int n)
(be sure your method is public)

Constraints

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

Examples

  1. 1

    Returns: 1

    One is the smallest squarefree number.

  2. 13

    Returns: 19

    See the list of squarefree numbers given in the problem statement.

  3. 100

    Returns: 163

  4. 1234567

    Returns: 2030745

  5. 1000000000

    Returns: 1644934081

  6. 90967

    Returns: 149622

  7. 11319

    Returns: 18611

  8. 513

    Returns: 839

  9. 11184

    Returns: 18386

  10. 375

    Returns: 614

  11. 138167024

    Returns: 227275651

  12. 424

    Returns: 694

  13. 24528128

    Returns: 40347210

  14. 29159607

    Returns: 47965587

  15. 1043

    Returns: 1713

  16. 239412989

    Returns: 393818515

  17. 416543150

    Returns: 685186026

  18. 997143

    Returns: 1640219

  19. 1168

    Returns: 1923

  20. 9777

    Returns: 16081

  21. 697611709

    Returns: 1147525338

  22. 831293191

    Returns: 1367422478

  23. 177

    Returns: 287

  24. 191425575

    Returns: 314882431

  25. 142779763

    Returns: 234863283

  26. 3814502

    Returns: 6274610

  27. 33096950

    Returns: 54442295

  28. 3884785

    Returns: 6390233

  29. 575209214

    Returns: 946181155

  30. 63881

    Returns: 105073

  31. 57053771

    Returns: 93849726

  32. 16973

    Returns: 27914

  33. 156221776

    Returns: 256974547

  34. 2620340

    Returns: 4310274

  35. 539

    Returns: 887

  36. 4329180

    Returns: 7121201

  37. 11595

    Returns: 19066

  38. 277268

    Returns: 456099

  39. 652494863

    Returns: 1073311086

  40. 844240558

    Returns: 1388720037

  41. 103244887

    Returns: 169830998

  42. 628220597

    Returns: 1033381445

  43. 1403692

    Returns: 2309001

  44. 922082415

    Returns: 1516764794

  45. 570889576

    Returns: 939075653

  46. 4270983

    Returns: 7025459

  47. 825196030

    Returns: 1357393089

  48. 220

    Returns: 362

  49. 162620192

    Returns: 267499497

  50. 56092

    Returns: 92262

  51. 284351294

    Returns: 467739070

  52. 18445

    Returns: 30335

  53. 1958283

    Returns: 3221258

  54. 117931104

    Returns: 193988937

  55. 43767868

    Returns: 71995151

  56. 590320058

    Returns: 971037565

  57. 78513

    Returns: 129138

  58. 966027

    Returns: 1589034

  59. 1185

    Returns: 1951

  60. 963135434

    Returns: 1584294294

  61. 1000000000

    Returns: 1644934081

  62. 999999999

    Returns: 1644934079

  63. 17

    Returns: 26

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: