Connection Status:
Competition Arena > SquareFree

SquareFree

SRM 190 · 2004-04-06 · by dgarthur

SRM 190 · 2004-04-06 · by dgarthur · Advanced Math
Class Name: SquareFree
Return Type: int
Method Name: getNumber
Arg Types: (int)
Problem Statement

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.

Constraints

  • n will be between 1 and 1,000,000,000 inclusive.
Examples
0)
1
Returns: 1

One is the smallest squarefree number.

1)
13
Returns: 19

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

2)
100
Returns: 163
3)
1234567
Returns: 2030745
4)
1000000000
Returns: 1644934081

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SquareFree with a public method int getNumber(int n) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous