Language: C++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
vector<int> C[(int)1e8+1];
int A[2000];
vector<int> R[2000];
bool used[2000], dead[2000];

vector<int> prime_list(int x) {
  vector<int> ret;
  for (int p=2; p*p<=x; p++) if (x%p == 0) {
    while (x%p == 0) x /= p;
    ret.pb(p);
  }
  if (x > 1) ret.pb(x);
  return ret;
}
int num = 0;
void dfs(int x);
void dfs2(int p) {
  vector<int> vs(C[p]);
  C[p].clear();
  for (int x : vs) dfs(x);
}
void dfs(int x) {
  assert(!dead[x]);
  if (used[x]) return;
  num--;
  used[x] = true;
  for (int p : R[x]) dfs2(p);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  vector<int> all;
  rep(i, N) cin >> A[i];
  sort(A, A+N);
  rep(i, N) R[i] = prime_list(A[i]), all.insert(all.end(), all(R[i]));
  sort(all(all)); uniq(all);

  vector<int> seq;
  rep(_, N) {
    num = N-_;
    for (int x : all) C[x].clear();
    rep(i, N) if (!dead[i]) used[i] = false;
    rep(i, N) if (!dead[i]) for (int p : R[i]) C[p].pb(i);
    int m = -1;
    rep(i, N) if (!dead[i]) {
      dfs(i);
      if (num == 0) {
        m = i;
        break;
      }
    }
    assert(m != -1);
    seq.pb(A[m]);
    dead[m] = true;
  }
  rep(i, N) cout << seq[i] << " "; cout << "\n";
  return 0;
}


Compiler output:
/tmp/ccpmts8z.o: in function `dfs(int)':
a.cc:(.text+0x1c9): relocation truncated to fit: R_X86_64_PC32 against symbol `dead' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x208): relocation truncated to fit: R_X86_64_PC32 against symbol `used' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x21a): relocation truncated to fit: R_X86_64_PC32 against symbol `num' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x223): relocation truncated to fit: R_X86_64_PC32 against symbol `num' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x22f): relocation truncated to fit: R_X86_64_PC32 against symbol `used' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x24d): relocation truncated to fit: R_X86_64_PC32 against symbol `R' defined in .bss section in /tmp/ccpmts8z.o
/tmp/ccpmts8z.o: in function `main':
a.cc:(.text+0x32a): relocation truncated to fit: R_X86_64_PC32 against symbol `A' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x365): relocation truncated to fit: R_X86_64_PC32 against symbol `A' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x372): relocation truncated to fit: R_X86_64_PC32 against symbol `A' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x39a): relocation truncated to fit: R_X86_64_PC32 against symbol `A' defined in .bss section in /tmp/ccpmts8z.o
a.cc:(.text+0x3c8): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status