def divisors(i):
    X=[]
    j=1
    while j*j<=i:
        if i%j==0:
            X.append(j)
            if j*j!=i:
                X.append(i//j)
        j+=1
    return X

N,M=map(int,input().split())
A=list(map(int,input().split()))

R=[0]*(N+1)
for a in A:
    R[a]=1

X=0
for i in range(N,0,-1):
    if R[i]==1:
        for j in divisors(i):
            R[j]=1-R[j]
    else:
        X+=1

print(X)