如果一开始就选择一个质数x，那该质数除一就一定满足条件，就应该发现(x+(x-1))/2也满足条件（除完之后还是那个质数，不变）（因为是向上取整），(x+(x-1)+(x+1))/3也满足条件，所以应该是选左然后选右然后再选左，然后再选右，尽量让质数多，可以一开始让x尽量往中间（n/2）靠

const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N];
void zhi()
{
    for (int i = 2; i <= 1e5; i++)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= 1e5 / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
void solve()
{
    int n; cin >> n;
    map<int, int> p;
    int x;
    for (int i = 0; i < cnt; i++)
    {
        if (prime[i] >= n / 2)
        {
            x = prime[i];
            break;
        }
    }
    int l = x - 1, r = x + 1;
    deque<int> q;
    q.push_back(x);
    while (l >= 1 || r <= n)
    {
        if (l >= 1) q.push_back(l), l--;
        if (r <= n) q.push_back(r), r++;
    }
    while (q.size()) cout << q.front() << " ", q.pop_front();
    cout << '\n';
}