import sys
import math

def main():
    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])) if M > 0 else []
    
    a_set = set(A) if M > 0 else set()
    
    # Precompute divisors for each k (d < k)
    divisors = [[] for _ in range(N+1)]
    for d in range(1, N+1):
        for k in range(2*d, N+1, d):
            divisors[k].append(d)
    
    # Precompute square numbers
    square = [False] * (N+1)
    for k in range(1, N+1):
        s = int(math.isqrt(k))
        if s * s == k:
            square[k] = True
    
    # Compute f(k) for each k
    f = [0] * (N+1)
    for k in range(1, N+1):
        if k in a_set:
            # f(k) = 1 if k is not square, else 0
            f[k] = 0 if square[k] else 1
        else:
            # f(k) = 1 if k is square, else 0
            f[k] = 1 if square[k] else 0
    
    x = [0] * (N+1)
    
    for k in range(1, N+1):
        sum_x = 0
        for d in divisors[k]:
            sum_x += x[d]
            sum_x %= 2
        x_k = (f[k] - sum_x) % 2
        x[k] = x_k
    
    print(sum(x))

if __name__ == "__main__":
    main()