import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
divs = defaultdict(list)
par = [0]*(N+1)

for i in range(1, N+1):
    for j in range(i, N+1, i):
        divs[j].append(i)
        par[i] ^= 1

A = list(map(int, input().split()))
s = set(A)
ans = 0

for i in range(N, 0, -1):
    if (par[i] and (i not in s)) or ((not par[i]) and (i in s)):
        ans += 1

        for j in divs[i]:
            par[j] ^= 1

print(ans)