Fişierul intrare/ieşire: | tygyn.in, tygyn.out | Sursă | Tuymaada 2019 |

Autor | Alexandru Petrescu | Adăugată de | Petrescu Alexandru •alexpetrescu |

Timp execuţie pe test | 0.7 sec | Limită de memorie | 262144 kbytes |

Scorul tău | N/A | Dificultate | N/A |

Vezi solutiile trimise | Statistici

# Tygyn

One of Marcel's ancestors, called Manchaary, son of Nyurgun and Sahayaana, was one of the servants of Tygyn Darkhan, at the beginning of the 17th century. Tygyn Darkhan, the great leader who unified the Yakutian tribes, seems to have been very passionate about Number Theory.

One day, he assigned some distinct integers from `2` to `M` to his `N` cows. He decided to group the cows, based on their numbers, into as few herds as possible. However, he set the following conditions that should be met for all herds:

- Let
`x`be the smallest number assigned to the cows in the herd. Each other number of a cow in the herd is of the form`x * k`, with`k`integer. - All divisors of
`k`(apart from`1`) are greater than or equal to any prime divisor of`x`, for all cows in the herd.

However, Tygyn is a bit busy with keeping peace in his territory, so he asked Manchaary to take care of the cows. The task was rather difficult for Manchaary, but the reward was magnificent: he could then marry beautiful Sardaana!

We know the end of the story: Manchaary solved the task and Sardaana became an ancestor of Marcel. However, when Marcel learned about the story, he thought the task can go back to the lands it originated. That is why the participants in Tuymaada 2019 have to solve it!

## Input

Input file `tygyn.in` contains on the first line the integer numbers `N` and `M`. The next line contains `N` numbers with values between `2` and `M`, representing the distinct numbers assigned to the `N` cows of Tygyn Darkhan.

## Output

Output file `tygyn.out` contains the minimal number of herds Manchaary could group the cows into.

## Constraints

`1 ≤ N < M ≤ 1.000.000`- For
`10`points,`M ≤ 20` - For
`40`points,`N ≤ 1.000` - Note that the scoring is not the same as the one in the official onsite contest

## Example

tygyn.in | tygyn.out |
---|---|

5 100 2 3 11 22 12 | 3 |

10 20 8 12 20 6 3 7 11 13 19 15 | 9 |

### Tutorial

You can see a `O(N + M)` solution description in problem's editorial

### Request

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.