시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 127 27 25 60.976%

문제

재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.

  1. 정수 N과 크기가 K인 배열 A을 정한다.
  2. 1부터 N까지 정수를 모두 종이에 쓴다.
  3. 배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.
  4. 배열이 비어있을 때 까지 3번을 반복한다.

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 15)

둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.

출력

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.

예제 입력 1

10 3
2 4 5

예제 출력 1

4

힌트

종이에는 1, 3, 7, 9가 남아있게 된다.