# Problem Link:

# Difficulty:

SIMPLE

# Pre-requisites:

Ad-hoc

# Problem:

Given integers **N** and **K**, pick **K** integers in 1…**N**, such that no two chosen integers are relatively prime.

# Explanation:

Let us try to construct a set of **K** integers such that no two are coprime. If we choose a number x (>1), and pick all multiples of x, then clearly no two of them will be coprime (all the numbers are divisible by x)! Thus, we can pick a set of size floor(**N**/x) having such a property. Thus, it is in our interest to have x small.

Indeed, if we pick x = 2, then for any **K** <= floor(**N**/2), we can just output the set 2, 4, 6, …, 2**K**. Hence, we have the sufficient condition when **K** <= floor(**N**/2).

It turns out that this sufficient condition is also necessary (almost). The fact is, when **K** > **N**/2, any set of size **K** will have some 2 consecutive elements. These consecutive elements will then be coprime.

The only special case is where (**N**, **K**) = (1, 1). In this case, since **K** = 1, we can output plate 1 and we’re done.

Formally, we can prove the necessity as follows:

If **K** = 1, we output 1 and we are done.

If **K** > 1, then we can can never have 1 in our set.

Then, from (2i, 2i+1), we can pick only one of the two. That is, we can pick only one from (2, 3), (4, 5), …, which gives us the bound of floor(**N**/2).

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here