import java.io.* import java.util.* import kotlin.math.* fun main() { // val T = nextInt() // repeat(T) {solve()} // pw.flush() solve() pw.flush() } fun solve() { val N = nextInt() val M = nextInt() val hs = HashSet() var mul = Array(N+1) {0} val div = Array(N+1) { mutableListOf() } var ans = 0 repeat(M) { hs.add(nextInt()) } for( i in 1..N ) { for( j in 1..N ) { if( i*j > N ) break mul[i*j]++ div[i*j].add(i) } } for( i in N downTo 1 ) { if( mul[i]%2 == 0 ) { ans++ for( d in div[i] ) mul[d]-- } } pw.println(ans) } fun printArray(a: Array) { a.forEach{ print("$it ") } println() } /* struct begin */ data class Pii(val fi: Int, val se: Int) data class Edge(val from: Int, val to: Int, val w: Long) class BinaryIndexedTree(n: Int) { val N = n var a = Array(N+1) {0L} fun sum(i: Int): Long { var idx = i+1 var res = 0L while( idx > 0 ) { res += a[idx] idx -= idx and (-idx) } return res } fun add(i: Int, x: Long) { var idx = i+1 while( idx <= N ) { a[idx] += x idx += idx and (-idx) } } } class UnionFind(N: Int) { var parent = Array(N) {it} var rank = Array(N) {1} var size = Array(N) {1} fun root(x: Int): Int { if( parent[x] == x ) { return x }else { parent[x] = root(parent[x]) return parent[x] } } fun unite(x: Int, y: Int) { val rx = root(x) val ry = root(y) if( rx == ry ) return if( rank[rx] > rank[ry] ) { parent[ry] = rx size[rx] += size[ry] }else { parent[rx] = ry size[ry] += size[rx] if( rank[rx] == rank[ry] ) rank[ry]++ } } fun same(x: Int, y: Int): Boolean = (root(x) == root(y)) fun getSize(x: Int): Int = size[root(x)] } /* struct end */ /* math begin */ fun intceil(x: Double) = ceil(x).toInt() fun intfloor(x: Double) = floor(x).toInt() fun gcd(x: Int, y: Int): Int { var a = max(x, y) var b = min(x, y) var r: Int do { r = a%b a = b b = r }while( r > 0 ) return a } /* math end */ /* I/O begin */ var st = StringTokenizer("") val br = System.`in`.bufferedReader() val pw = PrintWriter(System.out, false) fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine()!! fun nextDouble() = next().toDouble() fun nextIntarr(n: Int) = Array(n) {nextInt()} fun nextStrarr(n: Int) = Array(n) {next()} fun nextLongarr(n: Int) = Array(n) {nextLong()} fun next(): String { if( !st.hasMoreTokens() ) st = StringTokenizer(br.readLine()!!) return st.nextToken() } /* I/O end */