N,M = map(int, input().split())
A = list(map(int, input().split()))
P = [0] * (N+1)
B = [0] * (N+1)
for i in A:
    P[i] = 1
cnt = 0
for i in reversed(range(1,N+1)):
    if sum(B[::i]) & 1 != P[i]:
        B[i] = 1
    else:
        cnt += 1
print(cnt)