#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
const int MOD = 1000000007;

int main() {
    ll n;
    cin >> n;
    vector<ll> ans;
    FOR(i,2,((ll)sqrt(n))+1){
        ll j = i*i;
        while (j <= n){
            ans.push_back(j);
            j *= i;
        }
    }

    if (ans.size()==0){
        cout << n << endl;
        return 0;
    }

    sort(ALL(ans));
    ll cnt = 1;
    REP(i,ans.size()-1){
        if (ans.at(i) != ans.at(i+1)){
            cnt ++;
        }
    }
    cout << n - cnt << endl;
}
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int,int> ii;

const int N = 2005;
int n,a[N];
map<int,int> last;

int gcd(int a,int b) {
	return b ? gcd(b,a % b):a;
}

void local_run() {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	int mn = 1e9 + 7;
	for (int i = 1;i <= n;i++) {
		mn = min(mn,a[i]);
		for (int j = 1;j * j <= a[i];j++) {
			if (a[i] % j == 0) {
				last[j] = gcd(last[j],a[i]);
				last[a[i] / j] = gcd(last[a[i] / j],a[i]);
			}
		}
	}
	int ans = 1;
	for (ii x : last) {
		if (x.fi < mn && x.fi == x.se) ans++;
	}
	cout << ans;
}


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifdef localrun
		string f = "TEST";
		freopen(((string)f + ".inp").c_str(), "r", stdin);
		freopen(((string)f + ".out").c_str(), "w", stdout);
	#endif
	local_run();
}