#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>
using namespace std;
typedef long long LL;
#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;
// g++ -Wall -Wshadow -std=c++11 a.cpp && ./a.out
vector<int> primes(int n) {
vector<int> ans;
while (n % 2 == 0) {
ans.push_back(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0)
{
ans.push_back(i);
n = n/i;
}
}
if (n > 2)
ans.push_back(n);
return ans;
}
vector<int> uprimes(int n) {
vector<int> ans;
while (n % 2 == 0) {
if ((ans.size() && ans.back() != 2) || ans.size() == 0)
ans.push_back(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0)
{
if ((ans.size() && ans.back() != i) || ans.size() == 0)
ans.push_back(i);
// ans.push_back(i);
n = n/i;
}
}
if (n > 2)
ans.push_back(n);
return ans;
}
bool isprime(int n) {
vector<int> ans;
for (int i = 2; i <= sqrt(n); i = i + 2) {
if (n % i == 0)
{
return false;
}
}
return true;
}
int BITSET_SZ = 100000;
int main() {
std::ios::sync_with_stdio(false);cin.tie(0);
int n; cin>>n;
vector<int> nums;
vector<int> numcnt(1000001);
LL ans = 0;
LL ones = 0;
for (int i =0;i<n; i++) {
int nn; cin>>nn;
if (nn == 1) {
ones++;
continue;
}
nums.push_back(nn);
}
sort(nums.begin(), nums.end());
ans += ones * nums.size() + ones*(ones-1)/2;
vector<int> primes_under_1k;
vector<int> prime_to_idx(1000);
for (int i = 2; i <= 1000; i++) {
if (isprime(i)) {
primes_under_1k.push_back(i);
prime_to_idx[i] = primes_under_1k.size();
}
}
vector<bitset<100000>> bitsets(primes_under_1k.size());
for (int i = 0; i < nums.size(); i++) {
auto asd = uprimes(nums[i]);
bitset<100000> tmp;
int pi = 0;
for (; pi < asd.size() && asd[pi] < 1000; pi++) {
int idx = prime_to_idx[asd[pi]];
bitsets[idx].set(i);
tmp |= bitsets[idx];
}
int out = tmp.count() - 1;
for (; pi < asd.size(); pi++) {
int zxc = asd[pi];
while (zxc <= 1000000) {
if (numcnt[zxc]) {
for (int p : asd) {
if ((zxc % p)==0) {
out += numcnt[zxc];
}
}
}
zxc += asd[pi];
}
}
// cout << out << " isout " << nums[i] << " " << ans << endl;
numcnt[nums[i]]++;
int add = i-out;
ans += add;
}
cout << ans << endl;
// cout << test.size() << endl;
// for (int i =0;i<n;i++) {
// cin>>a[i];
// nums.insert(a[i]);
// }
// sort(a.begin(), a.end());
// LL ans = 0;
// for (int i=0;i<n;i++) {
// vector<int> ps = primes(a[i]);
// }
}