#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// ordered_set X;
// *X.find_by_order(i) = ith largest element (counting from zero)
// X.order_of_key(k) = number of items in X < k (strict lt)

ll gcd(ll a, ll b) {
    if (b > a) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    int N;
    cin >> N;

    vll A(N);
    for (int i=0;i<N;i++) cin >> A[i];

    unordered_set<ll> primes;
    vll Acpy(A.begin(), A.end());
    for (int i=0;i<N;i++) {
        for (int j=2;j*j<=Acpy[i];j++) {
            if (Acpy[i] % j == 0) {
                primes.insert(j);
                while (Acpy[i] % j == 0) Acpy[i] /= j;
            }
        }
        if (Acpy[i] > 1) primes.insert(Acpy[i]);
    }

    vll prs(primes.begin(), primes.end());
    int P = prs.size();

    vvi adj(N + P);

    // replace with sparsified graph
    for (int i=0;i<N;i++) {
        for (int j=0;j<P;j++) {
            if (A[i] % prs[j] == 0) {
                adj[i].push_back(N+j);
                adj[N+j].push_back(i);
            }
        }
    }

    // for (int i=0;i<N+P;i++) {
    //     cout << i << ": ";
    //     for (int v : adj[i]) cout << v << " ";
    //     cout << endl;
    // }

    vi comps(N + P, -1);
    vi smallest;
    int ncomps = 0;
    for (int i=0;i<N;i++) {
        if (comps[i] == -1) {
            comps[i] = ncomps;
            queue<int> bfs;
            bfs.push(i);

            int curmin = i;

            while (!bfs.empty()) {
                int cur = bfs.front();
                bfs.pop();

                if(cur < N && A[cur] < A[curmin]) curmin = cur;

                for (int nbr : adj[cur]) {
                    if (comps[nbr] == -1) {
                        comps[nbr] = ncomps;
                        bfs.push(nbr);
                    }
                }
            }

            smallest.push_back(curmin);
            ncomps++;
        }
    }

    priority_queue<pair<ll, int>> process;
    for (int i : smallest) {
        // cout << "adding " << A[i] << " " << i << endl;
        process.push({A[i], i});
    }

    vb dead(N+P, false);
    vi order;

    while (!process.empty()) {
        auto cur = process.top();
        process.pop();
        int v = cur.second;

        // cout << "processing " << A[v] << " " << v << endl;

        order.push_back(v);
        dead[v] = true;
        int curc = comps[v];

        for (int w : adj[v]) {
            if (comps[w] == curc) {
                comps[w] = ncomps;
                queue<int> bfs;
                bfs.push(w);

                vi cps;

                while (!bfs.empty()) {
                    int cur = bfs.front();
                    bfs.pop();

                    // cout << "bfs " << cur;
                    // if (cur < N) cout << " (A " << A[cur] << ")\n";
                    // else cout << " (P " << prs[cur-N] << ")\n";

                    if (cur >= N && (A[v] % prs[cur-N]) == 0) {
                        cps.push_back(cur);
                        // cout << "good prime" << endl;
                    }

                    for (int nbr : adj[cur]) {
                        if (!dead[nbr] && comps[nbr] == curc) {
                            comps[nbr] = ncomps;
                            bfs.push(nbr);
                        }
                    }
                }

                ll minval = 200000000ll;
                int minind = -1;
                for (int pi : cps) {
                    for (int r : adj[pi]) {
                        if (!dead[r] && A[r] < minval) {
                            minind = r;
                            minval = A[r];
                        }
                    }
                }

                ncomps++;
                if (minind != -1){
                    process.push({A[minind], minind});
                    // cout << "inserting " << minind << " (" << A[minind] << ")" << endl;
                } 
                
            }
        }

    }

    for (int i = 0; i<N;i++) cout << A[order[i]] << " \n"[i+1==N];

    return 0;

}


Measured memory_bytes: 640