N, K = map(int, input().split())
A = list(map(int, input().split()))
S = set(A)

cnt = [0] * (N + 1)
for i in range(1, N+1):
    for j in range(i, N+1, i):
        cnt[j] ^= 1

ans = 0
for i in range(1, N+1):
    if i in S and cnt[i] == 1:
        continue
    if not i in S and cnt[i] == 0:
        continue
    ans += 1
    for j in range(i, N+1, i):
        cnt[j] ^= 1

print(ans)