#[allow(unused_imports)] use std::io::{stdout, BufWriter, Write}; fn main() { let out = stdout(); let mut out = BufWriter::new(out.lock()); inputv! { n:usize,m:usize, } let k = input_vector::(); let mut v = vec![false; n + 1]; for i in k { v[i] = true; } let mut count = 0; for i in (1..v.len()).rev() { if v[i] { for k in i.get_divisor() { let k = k as usize; v[k] = !v[k]; } count += 1; } } writeln!(out, "{}", n - count).unwrap(); } //https://github.com/manta1130/competitive-template-rs use input::*; use primenumber::*; pub mod input { use std::cell::RefCell; use std::io; pub const SPLIT_DELIMITER: char = ' '; pub use std::io::prelude::*; thread_local! { pub static INPUT_BUFFER:RefCell>=RefCell::new(std::collections::VecDeque::new()); } #[macro_export] macro_rules! input_internal { ($x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { while p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .filter(|q| q.len() > 0) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let $x: $t = buf_split_result.parse().unwrap(); }; (mut $x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { while p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .filter(|q| q.len() > 0) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let mut $x: $t = buf_split_result.parse().unwrap(); }; } pub fn input_buffer_is_empty() -> bool { let mut empty = false; INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { empty = true; } }); empty } #[macro_export] macro_rules! inputv { ($i:ident : $t:ty) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty) => { input_internal!{mut $i : $t} }; ($i:ident : $t:ty $(,)*) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty $(,)*) => { input_internal!{mut $i : $t} }; (mut $i:ident : $t:ty,$($q:tt)*) => { input_internal!{mut $i : $t} inputv!{$($q)*} }; ($i:ident : $t:ty,$($q:tt)*) => { input_internal!{$i : $t} inputv!{$($q)*} }; } pub fn input_all() { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let mut temp_str = String::new(); std::io::stdin().read_to_string(&mut temp_str).unwrap(); let mut split_result_iter = temp_str .split_whitespace() .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); } pub fn input_line_str() -> String { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); s.trim().to_string() } #[allow(clippy::match_wild_err_arm)] pub fn input_vector() -> Vec where T: std::str::FromStr, { let mut v: Vec = Vec::new(); let s = input_line_str(); if s.is_empty() { return v; } let split_result = s.split(SPLIT_DELIMITER); for z in split_result { let buf = match z.parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } #[allow(clippy::match_wild_err_arm)] pub fn input_vector_row(n: usize) -> Vec where T: std::str::FromStr, { let mut v = Vec::with_capacity(n); for _ in 0..n { let buf = match input_line_str().parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } pub trait ToCharVec { fn to_charvec(&self) -> Vec; } impl ToCharVec for String { fn to_charvec(&self) -> Vec { self.to_string().chars().collect::>() } } } pub mod primenumber { use std::iter::Iterator; type ValueType = u64; pub trait GetDivisor { fn get_divisor(&self) -> Divisor; } macro_rules! GetDivisor_macro{ ($($t:ty),*) => { $( impl GetDivisor for $t { fn get_divisor(&self) -> Divisor { Divisor::calc(*self as ValueType) } })* }; } GetDivisor_macro!(u32, u64, u128, usize, i32, i64, i128, isize); pub trait GetPrimeFactorization { fn prime_factorization(&self) -> PrimeFactorization; } macro_rules! PrimeFactorization_macro{ ($($t:ty),*) => { $( impl GetPrimeFactorization for $t { fn prime_factorization(&self) -> PrimeFactorization { PrimeFactorization::calc(*self as ValueType) } })* }; } PrimeFactorization_macro!(u32, u64, u128, usize, i32, i64, i128, isize); pub struct Divisor { n: ValueType, cur: ValueType, flag: bool, } impl Divisor { pub fn calc(n: ValueType) -> Divisor { Divisor { n, cur: 1, flag: false, } } } impl Iterator for Divisor { type Item = ValueType; fn next(&mut self) -> Option { if self.cur * self.cur > self.n { None } else if self.flag { if self.cur * self.cur == self.n { return None; } self.flag = false; self.cur += 1; Some(self.n / (self.cur - 1)) } else { while self.n % self.cur != 0 { self.cur += 1; if self.cur * self.cur > self.n { return None; } } self.flag = true; Some(self.cur) } } } pub struct PrimeFactorization<'a> { n: ValueType, cur: ValueType, p_list: Option<&'a [ValueType]>, idx: usize, } impl<'a> PrimeFactorization<'a> { pub fn calc(n: ValueType) -> PrimeFactorization<'a> { PrimeFactorization { n, cur: 1, p_list: None, idx: 0, } } pub fn calc_fast(n: ValueType, p_list: &'a [ValueType]) -> PrimeFactorization<'a> { PrimeFactorization { n, cur: 1, p_list: Some(p_list), idx: 0, } } } impl<'a> Iterator for PrimeFactorization<'a> { type Item = ValueType; fn next(&mut self) -> Option { loop { if self.cur == 0 || self.cur > self.n { return None; } if self.p_list.is_some() { if self.idx >= self.p_list.unwrap().len() { return None; } self.cur = self.p_list.unwrap()[self.idx]; self.idx += 1; } else { self.cur += 1; } if self.cur * self.cur > self.n { if self.n != 1 { self.cur = 0; return Some(self.n); } return None; } if self.n % self.cur == 0 { self.n /= self.cur; if self.p_list.is_some() { self.idx -= 1; } self.cur -= 1; return Some(self.cur + 1); } } } } pub fn get_primelist(u: ValueType) -> Vec { let mut v = vec![true; u as usize + 1]; let mut r = vec![]; for i in 2..=u as usize { if v[i] { r.push(i as ValueType); let mut j = i * i; while j <= u as usize { v[j] = false; j += i; } } } r } pub fn get_mobius(n: ValueType) -> Vec { let mut r = vec![0, 1]; let p = get_primelist(n); for i in 2..=n { let mut f = PrimeFactorization::calc_fast(i as u64, &p).collect::>(); let count = f.len(); f.dedup(); if f.len() != count { r.push(0); } else { r.push(if f.len() % 2 == 0 { 1 } else { -1 }); } } r } fn modpow_128bit(mut s: u128, mut n: u128, p: u128) -> u128 { if p == 0 { return 1; } let mut t = s; s = 1; while n > 0 { if n & 1 != 0 { s *= t; s %= p; } n >>= 1; t *= t; t %= p; } s } fn modpow_64bit(mut s: u64, mut n: u64, p: u64) -> u64 { if p == 0 { return 1; } let mut t = s; s = 1; while n > 0 { if n & 1 != 0 { s *= t; s %= p; } n >>= 1; t *= t; t %= p; } s } pub fn miller_rabin(n: u64) -> bool { if n == 2 { return true; } if n == 1 || n % 2 == 0 { return false; } let (mut s, mut t) = (0, n - 1); while t % 2 == 0 { s += 1; t >>= 1; } let arr = if n < 4_759_123_141 { vec![2, 7, 61] } else if n < 341_550_071_728_321 { vec![2, 3, 5, 7, 11, 13, 17] } else if n < 3_825_123_056_546_413_051 { vec![2, 3, 5, 7, 11, 13, 17, 19, 23] } else { vec![2, 325, 9_375, 28_178, 450_775, 9_780_504, 1_795_265_022] } .iter() .filter(|&&q| q < n) .cloned() .collect::>(); let millor_rabin_inner = |a| { if modpow_128bit(a as u128, t as u128, n as u128) == 1 { return true; } for i in 0..s { if modpow_128bit(a as u128, 2_u128.pow(i) * t as u128, n as u128) as u64 == n - 1 { return true; } } false }; let millor_rabin_inner_small = |a| { if modpow_64bit(a, t, n) == 1 { return true; } for i in 0..s { if modpow_64bit(a, 2_u64.pow(i) * t, n) == n - 1 { return true; } } false }; if n < 1_000_000_000 { for a in arr { if !millor_rabin_inner_small(a) { return false; } } } else { for a in arr { if !millor_rabin_inner(a) { return false; } } } true } fn gcd_u64(a: u64, b: u64) -> u64 where { if b + b == b { return a; } gcd_u64(b, a % b) } pub struct PollardRho { arr: Vec, } impl PollardRho { pub fn calc(n: u64) -> PollardRho { PollardRho { arr: vec![n] } } } impl Iterator for PollardRho { type Item = ValueType; #[allow(clippy::many_single_char_names)] fn next(&mut self) -> Option { if self.arr.is_empty() || self.arr[0] == 0 { return None; } let n = self.arr.pop().unwrap(); if n == 1 { return None; } if miller_rabin(n) { let r = n; return Some(r); } if n % 2 == 0 { self.arr.push(n / 2); return Some(2); } let f = |x, seed| ((x as u128 * x as u128 + seed as u128) % n as u128) as u64; let f_small = |x, seed| ((x * x + seed) % n); for s in 1.. { let (mut x, mut y, mut d) = (2, 2, 1); while d == 1 { if n <= 1_000_000_000 { x = f_small(x, s); y = f_small(f_small(y, s), s); } else { x = f(x, s); y = f(f(y, s), s); } d = gcd_u64(std::cmp::max(x, y) - std::cmp::min(x, y), n) } if d != n { self.arr.push(n / d); self.arr.push(d); return self.next(); } } panic![] } } }