# TLE👹
import sys
readline = sys.stdin.readline
write = sys.stdout.write

# X, Y, E = map(int, readline().split())

class BipartiteMatching:
    def __init__(self, n):
        self.n=n  # n of vertices 
        self.graph=[[] for _ in range(n)]

    def add_edge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self,v,match,used):
        used[v]=True
        for u in self.graph[v]:
            w=match[u]
            if w<0 or (not used[w] and self.dfs(w,match,used)):
                match[v]=u
                match[u]=v
                return True
        return False

    def mactching(self):
        match=[-1]*self.n 
        for v in range(self.n):
            if match[v]>=0:
                continue 
            used=[False]*self.n
            self.dfs(v,match,used)
        return match



N = int(input())
A = list(map(int, input().split()))
MA = max(A)
L = [[] for _ in range(MA + 1)]
for i in range(1, N + 1):
    x = i
    while x <= MA:
        L[x].append(i)
        x += i
ok = 1
ng = N + 1
while (ng - ok) > 1:
    mid = (ok + ng) // 2
    bm = BipartiteMatching(mid+N)
    
    for i in range(N):
        for x in L[A[i]]:
            if(x <= mid):
                bm.add_edge(x - 1, mid + i)
            else:
                break
    match = bm.mactching()
    if(len(match) - match.count(-1) == mid * 2):
        ok = mid
    else:
        ng = mid

print(ok)