RelativelyPrimeSubset | Topcoder Archive

Problem Statement

You are given a int[] S containing a set of pairwise distinct positive integers.

Return the size of the largest subset T of S such that any two numbers from T are relatively prime.

Definition

Class:: RelativelyPrimeSubset
Method:: findSize
Parameters:: int[]
Returns:: int
Method signature:: int findSize(int[] S)
(be sure your method is public)

Notes

Two integers A and B are relatively prime if and only if their greatest common divisor equals to 1.

Constraints

S will contain between 1 and 50 elements, inclusive.
Each element of S will be between 1 and 100, inclusive.
All elements in S will be distinct.

Examples

```
{2,3,7,11,4}
```
```
Returns: 4
```
One such subset T is {2,3,7,11}, another is {3,4,7,11}.
```
{4,8,12,16}
```
```
Returns: 1
```
```
{100,17,81,82}
```
```
Returns: 3
```
```
{2,3,4,5,6}
```
```
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.