package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var n int64
var large []int64
var pref []uint32
var period int64
var goodPer int64
var ans int64

func g(x int64) int64 {
	if x < int64(len(pref)) {
		return int64(pref[int(x)])
	}
	q := x / period
	r := x % period
	return q*goodPer + int64(pref[int(r)])
}

func dfs(start int, x int64, sign int64) {
	ans += sign * g(x)
	for i := start; i < len(large); i++ {
		v := large[i]
		if v > x {
			break
		}
		dfs(i+1, x/v, -sign)
	}
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var k int
	fmt.Fscan(in, &n, &k)

	vals := make([]int, 0, k)
	hasOne := false

	for i := 0; i < k; i++ {
		var a int64
		fmt.Fscan(in, &a)
		if a == 1 {
			hasOne = true
		}
		if a > 1 && a <= n {
			vals = append(vals, int(a))
		}
	}

	if hasOne {
		fmt.Fprintln(out, 0)
		return
	}

	if len(vals) == 0 {
		fmt.Fprintln(out, n)
		return
	}

	sort.Ints(vals)

	const limit int64 = 10000000
	p := int64(1)
	s := 0
	for s < len(vals) && p*int64(vals[s]) <= limit {
		p *= int64(vals[s])
		s++
	}

	if s == 0 {
		period = 1
		goodPer = 1
		pref = make([]uint32, 1)
	} else {
		period = p
		build := p
		if build > n {
			build = n
		}
		m := int(build)
		bad := make([]byte, m+1)
		for i := 0; i < s; i++ {
			a := vals[i]
			for j := a; j <= m; j += a {
				bad[j] = 1
			}
		}
		pref = make([]uint32, m+1)
		var cnt uint32
		for i := 1; i <= m; i++ {
			if bad[i] == 0 {
				cnt++
			}
			pref[i] = cnt
		}
		if build == p {
			goodPer = int64(cnt)
		}
	}

	large = make([]int64, len(vals)-s)
	for i := s; i < len(vals); i++ {
		large[i-s] = int64(vals[i])
	}

	dfs(0, n, 1)
	fmt.Fprintln(out, ans)
}