#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
	while (b) a %= b, swap(a, b); return a;
}
template <class T, T(*op)(T, T), T ident>
struct SegmentTree {
	int n; vector<T> tree;
	SegmentTree(int _n) : n(_n), tree(2 * n, ident) { }
	void update(int i, T val) {
		for (tree[i+n] = val, i = (i+n)/2; i > 0; i /= 2)
			tree[i] = op(tree[2*i], tree[2*i+1]);
	}
	T query(int l, int r) {
		T lhs = T(ident), rhs = T(ident);
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (  l&1 ) lhs = op(lhs, tree[l++]);
			if (!(r&1)) rhs = op(tree[r--], rhs);
		}
		return op(l == r ? op(lhs, tree[l]) : lhs, rhs);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N;
	cin >> N;

	vector<ll> A;
	ll last = -1LL;
	unordered_set<ll> gcds;
	for (int i = 0; i < N; ++i) {
		ll v;
		cin >> v;
		if (v != last) A.push_back(v), gcds.insert(v);
	}
	N = (int)A.size();

	SegmentTree<ll, gcd, 0LL> st(A.size());
	for (size_t i = 0; i < A.size(); ++i) st.update(i, A[i]);

	for (int Q = 4000000; Q-->0;) {
		int l = rand() % N, r = rand() % N;
		gcds.insert(st.query(min(l, r), max(l, r))); 
	}
	cout << gcds.size() << endl;

	return 0;
}