#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

template <class T> T power(T a, long long e, T m) {
  for (T b = 1; ; (a *= a) %= m) {
    if (e & 1) (b *= a) %= m;
    if (!(e >>= 1)) return b;
  }
}

long long gcd(long long a, long long b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a == 0) return b;
  if (b == 0) return a;
  const int s = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do {
    b >>= __builtin_ctzll(b);
    if (a > b) swap(a, b);
    b -= a;
  } while (b);
  return a << s;
}

bool isPrime(long long n) {
  if (n <= 1 || n % 2 == 0) return (n == 2);
  const int s = __builtin_ctzll(n - 1);
  const long long d = (n - 1) >> s;
  // http://miller-rabin.appspot.com/
  for (const long long base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
    __int128 a = base % n;
    if (a == 0) continue;
    a = power<__int128>(a, d, n);
    if (a == 1 || a == n - 1) continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      (a *= a) %= n;
      if (a == n - 1) {
        ok = true;
        break;
      }
    }
    if (!ok) return false;
  }
  return true;
}

// n >= 3, odd
void factorizeRec(long long n, vector<long long> &ps) {
  static constexpr int BLOCK = 256;
  if (isPrime(n)) {
    ps.push_back(n);
  } else {
    for (long long c = 2; ; ++c) {
      long long x, y = 2, y0, z = 1, d = 1;
      for (int l = 1; d == 1; l <<= 1) {
        x = y;
        for (int i = 0; i < l; ++i) y = (static_cast<__int128>(y) * y + c) % n;
        for (int i = 0; i < l; i += BLOCK) {
          y0 = y;
          for (int j = 0; j < BLOCK && j < l - i; ++j) {
            y = (static_cast<__int128>(y) * y + c) % n;
            z = (static_cast<__int128>(z) * (y - x)) % n;
          }
          if ((d = gcd(z, n)) != 1) break;
        }
      }
      if (d == n) {
        for (y = y0; ; ) {
          y = (static_cast<__int128>(y) * y + c) % n;
          if ((d = gcd(y - x, n)) != 1) break;
        }
      }
      if (d != n) {
        factorizeRec(d, ps);
        factorizeRec(n / d, ps);
        return;
      }
    }
  }
}

vector<pair<long long, int>> factorize(long long n) {
  vector<pair<long long, int>> pes;
  if (n >= 2) {
    const int s = __builtin_ctzll(n);
    if (s) pes.emplace_back(2, s);
    if (n >> s >= 2) {
      vector<long long> ps;
      factorizeRec(n >> s, ps);
      std::sort(ps.begin(), ps.end());
      const int psLen = ps.size();
      for (int i = 0, j = 0; i < psLen; i = j) {
        for (; j < psLen && ps[i] == ps[j]; ++j) {}
        pes.emplace_back(ps[i], j - i);
      }
    }
  }
  return pes;
}

vector<long long> divisors(long long n) {
  const auto pes = factorize(n);
  vector<long long> ds{1};
  for (const auto &pe : pes) {
    const int len0 = ds.size();
    const int len1 = len0 * (pe.second + 1);
    ds.resize(len1);
    for (int i = len0; i < len1; ++i) ds[i] = ds[i - len0] * pe.first;
  }
  std::sort(ds.begin(), ds.end());
  return ds;
}

////////////////////////////////////////////////////////////////////////////////

// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
  // Watch out when using types other than int and long long.
  static constexpr Flow FLOW_EPS = 1e-10L;
  static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
  static constexpr Cost COST_EPS = 1e-10L;
  static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();

  int n, m;
  vector<int> ptr, nxt, zu;
  vector<Flow> capa;
  vector<Cost> cost;

  explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
  void ae(int u, int v, Flow w, Cost c) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w);
    nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
    nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
  }

  vector<Cost> pot, dist;
  vector<bool> vis;
  vector<int> pari;

  // cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
  vector<Flow> flows;
  vector<Cost> slopes;

  // Finds a shortest path from s to t in the residual graph.
  // O((n + m) log m) time.
  //   Assumes that the members above are set.
  //   The distance to a vertex might not be determined if it is >= dist[t].
  //   You can pass t = -1 to find a shortest path to each vertex.
  void shortest(int s, int t) {
    using Entry = pair<Cost, int>;
    priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
    for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
    for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
      const Cost c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (vis[u]) continue;
      vis[u] = true;
      if (u == t) return;
      for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
        const int v = zu[i];
        if (!vis[v]) {
          const Cost cc = c + cost[i] + pot[u] - pot[v];
          if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
        }
      }
    }
  }

  // Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
  //   Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
  //   edge, or cannot stop if there exists a negative-cost cycle.
  //   min{(max flow), limFlow} shortest paths if Flow is an integral type.
  pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
    assert(0 <= s); assert(s < n);
    assert(0 <= t); assert(t < n);
    assert(s != t);
    assert(0 <= limFlow);
    pot.assign(n, 0);
    for (; ; ) {
      bool upd = false;
      for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
        const int u = zu[i ^ 1], v = zu[i];
        const Cost cc = pot[u] + cost[i];
        if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
      }
      if (!upd) break;
    }
    dist.resize(n);
    vis.resize(n);
    pari.resize(n);
    Flow totalFlow = 0;
    Cost totalCost = 0;
    flows.clear(); flows.push_back(0);
    slopes.clear();
    for (; totalFlow < limFlow; ) {
      shortest(s, t);
      if (!vis[t]) break;
      for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
      Flow f = limFlow - totalFlow;
      for (int v = t; v != s; ) {
        const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
      }
      for (int v = t; v != s; ) {
        const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
      }
      totalFlow += f;
      totalCost += f * (pot[t] - pot[s]);
      flows.push_back(totalFlow);
      slopes.push_back(pot[t] - pot[s]);
    }
    return make_pair(totalFlow, totalCost);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N;
vector<int> A;

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    
    vector<vector<Int>> pss(N);
    vector<int> ds;
    vector<pair<int, int>> dis;
    for (int i = 0; i < N; ++i) {
      const auto pes = factorize(A[i]);
      for (const auto &pe : pes) {
        pss[i].push_back(pe.first);
      }
      const auto divs = divisors(A[i]);
      for (const Int d : divs) {
        ds.push_back(d);
        dis.emplace_back(d, i);
      }
    }
    sort(ds.begin(), ds.end());
    ds.erase(unique(ds.begin(), ds.end()), ds.end());
    reverse(ds.begin(), ds.end());
    sort(dis.begin(), dis.end());
    const int dsLen = ds.size();
    auto id = [&](int d) -> int {
      return lower_bound(ds.begin(), ds.end(), d, greater<int>{}) - ds.begin();
    };
cerr<<"|ds| = "<<dsLen<<endl;
// cerr<<"ds = "<<ds<<endl;
    
    MinCostFlow<int, int> mcf(dsLen + 2);
    const int s = dsLen, t = dsLen + 1;
    for (int i = 0; i < N; ++i) {
      const int u = id(A[i]);
      mcf.ae(s, u, 1, 0);
    }
    for (int u = 0; u < dsLen; ++u) {
      auto it = lower_bound(dis.begin(), dis.end(), make_pair(ds[u], -1));
// cerr<<ds[u]<<" "<<pss[it->second]<<endl;
      for (const auto &p : pss[it->second]) {
        if (ds[u] % p == 0) {
          const int v = id(ds[u] / p);
          mcf.ae(u, v, N, -1);
        }
      }
    }
    for (int u = 0; u < dsLen; ++u) {
      mcf.ae(u, t, 1, 0);
    }
    const auto res = mcf.run(s, t, N);
    printf("%d\n", -res.second);
    assert(res.first == N);
  }
  return 0;
}