#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long 

const int N=1e6+5,M=31623;
const ll inf=1e9;
int n,m,idx=0,prm[N],cnt=0,ct[N];
bool vis[N];
gp_hash_table<int,int> mp;

namespace MCMF{
  int S,T,head[N],tot=1,cur[N];
  ll dis[N];
  bool vis[N];
  struct Edge{
  	int v,nxt;
  	ll w,c;
  }e[N<<1];
  
  void add(int u,int v,int w,int c){
  	e[++tot]={v,head[u],w,-c};head[u]=tot;
  	e[++tot]={u,head[v],0,c},head[v]=tot;
  }
  
  bool spfa(){
  	for(int i=S;i<=T;i++) dis[i]=inf,cur[i]=head[i],vis[i]=false;
  	queue<int> Q;
  	dis[S]=0,Q.push(S),vis[S]=1;
  	while(!Q.empty()){
  	  int u=Q.front();Q.pop();
	  vis[u]=0;
	  for(int i=head[u];i;i=e[i].nxt){
	  	int v=e[i].v;ll w=e[i].w,c=e[i].c;
	  	if(w&&dis[v]>dis[u]+c){
	  	  dis[v]=dis[u]+c;
		  if(!vis[v]) Q.push(v),vis[v]=1;	
		}
	  }	
	}
	return dis[T]!=inf;
  }
  
  ll dfs(int u,ll flow){
  	if(u==T||!flow) return flow;
  	ll res=flow;
  	vis[u]=1;
	for(int i=cur[u];i&&res;i=e[i].nxt){
  	  cur[u]=i;
  	  int v=e[i].v;ll w=e[i].w,c=e[i].c;
  	  if(!vis[v]&&w&&dis[v]==dis[u]+c){
  	    ll f=dfs(v,min(w,res));
		res-=f,e[i].w-=f,e[i^1].w+=f;	
	  }
	}
	return flow-res;
  }
  
  ll dinic(){
  	ll res=0,ans=0;
  	while(spfa()){
  	  ll flow=dfs(S,inf);
	  res+=flow,ans+=flow*dis[T];	
	}
	return ans;
  }
}

void init(){
  for(int i=2;i<=M;i++){
    if(!vis[i]) prm[++cnt]=i;
    for(int j=1;j<=cnt&&i*prm[j]<=M;j++){
      vis[i*prm[j]]=1;
      if(i%prm[j]==0) break;
    }
  }
}

int Count(int x){
  int res=0;
  for(int i=1;i<=cnt&&prm[i]<=x;i++) while(x%prm[i]==0) x/=prm[i],++res;
  if(x>1) ++res;
  return res;
}

void wrk(int i,int j,int nw){
  if(mp.find(j)==mp.end()) mp[j]=++idx,ct[idx]=Count(j);
  MCMF::add(i,mp[j],1,nw-ct[mp[j]]);
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;MCMF::S=0,idx=n;init();
  for(int i=1,x;i<=n;i++){
    cin>>x,MCMF::add(MCMF::S,i,1,0);
    int nw=Count(x);
    for(int j=1;j*j<=x;j++) if(x%j==0){
      wrk(i,j,nw);
      if(j*j!=x) wrk(i,x/j,nw);
    }
  }
  MCMF::T=++idx;
  for(int i=n+1;i<idx;i++) MCMF::add(i,idx,1,0);
  cout<<-MCMF::dinic();
  return 0;
}