/**
 *    author:  avoas
 *    created: 02.03.2021 18:53:30
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(x) (x).begin(),(x).end()

#define int long long

constexpr double EPS = 1e-12;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    set<int> s;

    for(int a = 2; a*a <= n; a++){
        int b = 2;
        while(pow(a,b) <= n){
            s.insert(pow(a,b));
            b++;
        }
    }
    int ans = n - s.size();
    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define POPCOUNT(x) __builtin_popcount(x)
template <typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template <typename T> void chmax(T &a, const T &b) { a = max(a, b); }

const ll INF = 1LL << 60;

struct FastIO {
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }
} fastiofastio;

const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// BEGIN CUT
ll modpow(ll x, ll y, ll m) {
    ll a = 1, p = x;
    while (y > 0) {
        if (y % 2 == 0) {
            p = (p * p) % m;
            y /= 2;
        } else {
            a = (a * p) % m;
            y--;
        }
    }
    return a;
}
// END CUT

unordered_map<ll, ll> t;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    sort(ALL(A));
    REP(i, N) {
        for (ll d = 1; d * d <= A[i]; d++) {
            if (A[i] % d == 0) {
                if (t.count(d) == 0) {
                    t[d] = A[i];
                } else {
                    t[d] = gcd(t[d], A[i]);
                }
                if (t.count(A[i] / d) == 0) {
                    t[A[i] / d] = A[i];
                } else {
                    t[A[i] / d] = gcd(t[A[i] / d], A[i]);
                }
            }
        }
    }
    ll ans = 0;
    for (auto p : t) {
        if (p.first <= A[0] && p.first == p.second)
            ans++;
    }
    cout << ans << endl;
}