import math
import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+M]))
    
    A_set = set(A)
    A_sorted = A  # already sorted as per input constraints
    
    sum_ = [0] * (N + 2)  # sum_1 to sum_N
    total_skipped = 0
    
    for k in range(1, N + 1):
        s = int(math.isqrt(k))
        is_square = (s * s == k)
        pos = bisect.bisect_left(A_sorted, k)
        in_A = pos < M and A_sorted[pos] == k
        
        # Calculate c_k
        if in_A:
            c_k = 0 if is_square else 1
        else:
            c_k = 1 if is_square else 0
        
        current_sum = sum_[k]
        x_k = (c_k - current_sum) % 2
        total_skipped += x_k
        
        # Update sum for multiples of k
        if x_k == 1:
            multiple = 2 * k
            while multiple <= N:
                sum_[multiple] ^= 1
                multiple += k
    
    print(total_skipped)

if __name__ == '__main__':
    main()