1443A - Kids Seating

(Disclaimer: I came with an uglier $O(n^2 \log{n})$ solution, but a good friend of mine pointed out that I was doing unnecessary computation. Anyway, this is the improved version.)

First, note that the seats must be composite numbers that share a factor but are not multiples of themselves.

So, our answer has to be a subset of the multiples of some prime in [1, 4n].

Furthermore, note that one of the best candidates to fulfill this common-factor role is 2, since there are more multiples of 2 than any other prime in that range.

Finally, note that it is always better to pick bigger numbers than smaller numbers, because they are less likely to be multiples of each other.

Our final answer is:

This subset of $n$ numbers have a common factor of 2 and are definitely not multiples of each other. If you’re not convinced of this last fact, think that any multiple of one of these numbers will necessarily exceed 4n, therefore not be in the chosen subset.

Time complexity: $O(n)$

Memory complexity: $O(1)$

using namespace std;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 2 * n + 2; i <= 4 * n; i += 2)
            cout << i << " ";
        cout << endl;
    }
    return 0;
}