n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)

# max_fac[x] 表示数值x的最大质因数
max_fac = [-1 for _ in range(10001)]

for i in range(2, 10001):
    if max_fac[i] == -1:
        for val in range(i, 10001, i):
            # 枚举所有i的倍数，更新这些倍数的最大质因子
            max_fac[val] = i


# 是否互质
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def is_valid(a, b):
    val = a
    fac = set()
    while val != 1:
        p = max_fac[val]
        while max_fac[val] == p:
            val //= p
        fac.add(p)

    val = b
    while val != 1:
        p = max_fac[val]
        while max_fac[val] == p:
            val //= p
        if p in fac:
            return False
    return True


min_group_cnt = [0x7fffffff]
group = [[] for i in range(11)]
visit = [0] * 11        # 位置是否被选


# 进行递归搜索，枚举当前组要选择的数字，要么不选数字新增加一个组，要么选数字放到最后一个组
# cur_idx 当前从哪个位置开始选   group_idx 当前在选哪个组的数据 cnt 当前已经被选的数字个数
def dfs(val_idx, group_idx, cnt):
    #print(group[:group_idx+1])

    if group_idx + 1 >= min_group_cnt[0]:
        return

    if cnt == len(arr):
        group_num = group_idx if len(group[group_idx]) == 0 else group_idx+1
        min_group_cnt[0] = min(min_group_cnt[0], group_num)
        return

    add_data = False
    for idx in range(val_idx, len(arr)):
        if visit[idx] == 1:
            continue

        new_val = arr[idx]
        if len(group[group_idx]) == 0 and group_idx-1 >= 0 and new_val > group[group_idx-1][0]:
            # 保证枚举在组合组之间是组合型枚举，避免重复枚举
            continue

        flag = True
        for val in group[group_idx]:
            if not is_valid(val, new_val):
                flag = False
                break

        if flag:
            add_data = True
            visit[idx] = 1
            group[group_idx].append(new_val)
            dfs(val_idx+1, group_idx, cnt+1)
            group[group_idx].pop(-1)
            visit[idx] = 0

    # 新开一个组
    if len(group[group_idx]) > 0 and add_data == False:
        dfs(0, group_idx + 1, cnt)


dfs(0, 0, 0)
print(min_group_cnt[0])