import sys
input = sys.stdin.readline


N,M=map(int,input().split())
A=set(map(int,input().split()))
ans=0
sabo = set()
for i in range(N,0,-1):
    l=0
    j=i
    while j<=N:
        if j not in sabo:
            l^=1
        j+=i
    if l ^ (i in A):
        ans+=1
        sabo.add(i)
print(ans)