def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+M]))
    
    s = [0] * (N + 1)
    for a in A:
        s[a] = 1
    
    sum_div = [0] * (N + 2)
    x = [0] * (N + 2)
    
    for k in range(1, N + 1):
        sum_so_far = sum_div[k]
        xk = (s[k] - sum_so_far) % 2
        x[k] = xk
        
        m = 2 * k
        while m <= N:
            sum_div[m] = (sum_div[m] + xk) % 2
            m += k
    
    ans = sum(1 - x[i] for i in range(1, N + 1))
    print(ans)
    
if __name__ == "__main__":
    main()