from sympy import prime def make_divisors(n): divisors = [] for i in range(1, int(n**0.5)+1): if n % i == 0: divisors.append(i) if i != n // i: divisors.append(n//i) divisors.sort() return divisors n,m = map(int,input().split()) a = [int(i) for i in input().split()] A = [0]*(n+1) for i in range(m): A[a[i]] = 1 #print(A) li = [0]*(n+1) ans = 0 for i in range(n,0,-1): if A[i] != li[i]: for j in make_divisors(i): li[j] += 1 li[j] %= 2 else: ans += 1 print(ans)