#include<bits/stdc++.h>
#define pb push_back
#define pf push_front

using namespace std;	
typedef long long int lli;
lli n,k,m,t,a,b,l,r,h,u,x,y,temp1,temp2,temp,q,d,mod=1e9+7,w,p,c,z;

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n;
    
    vector<lli>v(n+2);
    lli mn = 1e9+7;
    
    for(int i=0;i<n;i++)
	{
		cin>>v[i];
		mn = min(mn,v[i]);
	}
    
    unordered_map<lli,lli>mp;
    
    for(auto x:v)
    {
    	lli sq = sqrt(x);
    	
    	for(int i=1;i<=sq;i++)
    	{
    		if( x%i == 0 )
    		{
    			if(mp.find(i) == mp.end())
    			{
    				mp[i] = x;
    			}
    			else
    			{
    				mp[i] = gcd(mp[i], x);
				}
				
				if(mp.find(x/i) == mp.end())
    			{
    				mp[x/i] = x;
    			}
    			else
    			{
    				mp[x/i] = gcd(mp[x/i], x);
				}
    		}
    	}
    }
    
    lli ans = 0;
    
    for(auto x:mp)
    {
    	if(x.first 	<= mn)
    	{
    		if(x.second == x.first) ans++;
    	}
    }
    
    cout<<ans<<endl;
}

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;


const int M = 1e5;
int main() 
{
    int n;
    cin >> n;
    vector<int> t(n);
    rep(i, n) cin >> t[i];
    int sum = 0;
    rep(i, n) sum += t[i];

    vector<vector<int>> dp(n+5, vector<int>(2*M,-1));

    dp[0][0] = 1;
    rep(i, n)
    {
        rep(j, M + 2)
        {
            dp[i + 1][j] = max(dp[i][j],dp[i+1][j]);
            dp[i + 1][j + t[i]] = max(dp[i][j], dp[i + 1][j+t[i]]);
        }
    }
    int ans = M;
    rep(i, M)
    {
        if (dp[n][i] == 1)
        {
            int a = i;
            int b = sum - i;
            ans = min(ans, max(a, b));
        }
    }
    cout << ans << endl;
   
    return 0;
}
