#include<bits/stdc++.h>
#define N 50005
using namespace std;
typedef long long ll;
int n,a[N],g[N],f[N],vis[N],cnt;
ll ans,sum;
int gcd(int x,int y){if(!y)return x;return gcd(y,x%y);}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘);
    do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘);
    return f*x;
}
int prime[N];
void calcpri(){
    memset(vis,1,sizeof(vis));
    for(int i=2;i<=5000;i++){
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            int t=i*prime[j];if(t>5000)break;
            vis[t]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){
    n=read();for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<n;i++)g[i]=gcd(a[i],a[i+1]);
    calcpri();
    for(int i=1;i<=cnt;i++){
        memset(f,0,sizeof(f));
        for(int j=1;j<n;j++)while(g[j]%prime[i]==0)f[j]++,g[j]/=prime[i];
        sum=0;
        for(int j=1;j<n;j++){
            sum+=f[j];int w=f[j];f[j]=0;
            w=min(w,f[j+1]);f[j+1]-=w;
            w=min(w,f[j+2]);f[j+2]-=w;
        }
        ans+=1LL*prime[i]*sum;
    }
    for(int i=1;i<n;i++){
        if(g[i]>1){
            ans+=g[i];if(g[i+2]==g[i]&&g[i+1]==g[i])g[i+2]=1;
            if(g[i+1]==g[i])g[i+1]=1;g[i]=1;
        }
    }
    cout<<ans<<endl;
}