【cf 1176 D】Recover it!

#include <bits/stdc++.h>
using namespace std;
const int N = 3750131;
int n, a[N], id[N], used[N], prime[N];
#pragma warning(disable:4996)
int findMax(int x)
{
  for (int i = 2; i * i <= x; i++)
  {
    if (x % i == 0)return x / i;
  }
  return 0;
}
int main()
{
  vector<int>p;
  int cnt = 0;
  for (int i = 2; i <= N; i++)
  {
    if (!used[i])
    {
      prime[++cnt] = i;
      id[i] = cnt;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
    {
      used[i * prime[j]] = 1;
      if (i % prime[j] == 0)break;
    }
  }
  int n;
  scanf("%d", &n);
  n *= 2;
  for (int i = 1; i <= n; i++)
  {
    int v;
    scanf("%d", &v);
    a[v]++;
  }
  vector<int>res;
  for (int i = N - 1; i >= 2; i--)
  {
    if (!a[i])continue;
    while (a[i] > 0)
    {
      if (!used[i])
      {
        res.push_back(id[i]);
        a[id[i]]--;
      }
      else
      {
        res.push_back(i);
        a[findMax(i)]--;
      }
      a[i]--;
    }
  }
  for (int x : res)
    cout << x << " ";
  cout << endl;
  return 0;
}