Problem D - round #565 CF

#include <bits/stdc++.h>

#define SYNC ios::sync_with_stdio(0);
#define F first
#define S second
#define endl '\n'


using namespace std;

using ll = long long int;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const int MAXN = 199999;
const ll mod = 1000000007;
const double eps = 0.000000001;


int largest_divisor(int n) {
  if (n % 2 == 0) {
    return n/2;
  }

  int sq = sqrt(n);
  for (int i = 3; i <= sq; i += 2) {
    if (n % i == 0) {
      return n/i;
    }
  }
  return 1;

}

bool is_prime(int n) {
  if (n <= 3) {
    return n > 1;
  }
  if (n % 2 == 0 || n % 3 == 0) {
    return false;
  }
  for (int i = 5; i * i <= n ;i += 6) {
    if (n % i == 0 || n % (i+2) == 0) {
      return false;
    }

  }
  return true;
}

int primes_to_idx[2750132];
int freq[2750132];

int main() {
  ios::sync_with_stdio(0);
  for (int i = 0, j = 1; j <= MAXN; i++) {
    if (is_prime(i)) {
      primes_to_idx[i] = j;
      j++;
    }
  }
  int n;
  cin >> n;
  for (int i = 0, num; i < 2*n; i++) {
    cin >> num;
    freq[num]++;
  }
  vector<int> ans;

  for (int i = 2750131; i >= 0; --i) {
    if (freq[i]) {
      int ld = largest_divisor(i);
      if (ld == 1) {
        freq[primes_to_idx[i]] -= freq[i];
        for (int j = 0; j < freq[i]; j++) ans.push_back(primes_to_idx[i]);
        freq[i] = 0;
      } else {
        for (int j = 0; j < freq[i]; j++) ans.push_back(i);
        freq[ld] -= freq[i];
        freq[i] = 0;
      }
    }
  }
  for (auto a: ans) cout << a << ' ';
  cout << endl;

}