从$[1…n]$里挑$k$个数使得$gcd(a_i,a_j)$最大值最小。

$gcd=1$的时候，选择所有质数。然后再选择$2$的倍数，发现只能选择因数$\leq 2$。然后选择$3$的倍数，且因数$\leq 3$。选择某个数的时候，其$gcd$就是那个数的最大因数。即处理所有的数最大的因数。桶排一下即可。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int n, num[N], d[N];
int main()
{
cin >> n;
d[1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = i + i; j <= n; j += i)
d[j] = i;
}
for (int i = 1; i <= n; i++)
num[d[i]]++;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= num[i]; j++)
if (i != 1 || j != 1)
printf(“%d “, i);
}
}