Indivisible | Topcoder Archive

Problem Statement

Given a positive integer n, you are to find the largest subset S of {1,...,n} such that no member of S is divisible by another member of S. If there is more than one subset of the maximum size, choose the lexicographically earliest such subset. A subset S is lexicographically earlier than a subset T if the smallest element that is a member of one of the subsets, but not both, is a member of S. Return the subset S as a int[] in increasing order.

Definition

Class:: Indivisible
Method:: largestSubset
Parameters:: int
Returns:: int[]
Method signature:: int[] largestSubset(int n)
(be sure your method is public)

Constraints

n is between 1 and 1000, inclusive.

Examples

```
10
```
```
Returns: {4, 5, 6, 7, 9 }
```
There are several possible subsets of size 5, such as { 4,6,7,9,10 }, but { 4,5,6,7,9 } is the lexicographically earliest.
```
1
```
```
Returns: {1 }
```
```
5
```
```
Returns: {2, 3, 5 }
```

Returns: {4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 23 }

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.