import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split())) if m > 0 else []
    a_exists = [False] * (n + 1)
    for a in A:
        a_exists[a] = True

    # Precompute divisors for each x where d < x and d divides x
    divisors = [[] for _ in range(n + 1)]
    for d in range(1, n + 1):
        multiple = d * 2
        while multiple <= n:
            divisors[multiple].append(d)
            multiple += d

    # Precompute square checks
    is_square = [False] * (n + 1)
    for x in range(1, n + 1):
        s = int(x ** 0.5)
        if s * s == x:
            is_square[x] = True

    # Calculate c for each x
    c = [0] * (n + 1)
    for x in range(1, n + 1):
        t = 1 if is_square[x] else 0
        b = 1 if a_exists[x] else 0
        c[x] = (t - b) % 2

    # Calculate X for each x
    X = [0] * (n + 1)
    for x in range(1, n + 1):
        sum_d = 0
        for d in divisors[x]:
            sum_d = (sum_d + X[d]) % 2
        X[x] = (c[x] - sum_d) % 2

    # Count the number of students who skipped
    count = 0
    for x in range(1, n + 1):
        if X[x]:
            count += 1
    print(count)

if __name__ == "__main__":
    main()