{"code":"ntthuaso","name":"Thừa số nguyên tố nhỏ nhất","description":"**JOIN TỔ CHỨC ĐỂ THAM GIA CÁC KÌ THI THỬ HSG 8,9** [Bấm vào đây][1]\r\nVới một số nguyên dương $P$ $(P \\geq 2)$, ta có thể phân tích $P$ thành tích các thừa số nguyên tố, trong đó có một thừa số nguyên tố nhỏ nhất.\r\n**Ví dụ** $100 = 2 \\times 2 \\times 5 \\times 5$ thì $2$ là thừa số nguyên tố nhỏ nhất của $100$; $15 = 3  \\times 5$ thì $3$ là thừa số nguyên tố nhỏ nhất của $15$; $17 = 17$ thì $17$ là thừa số nguyên tố nhỏ nhất của $17$.\r\nCho trước một dãy gồm $n$ số nguyên tố $a_1,a_2,...,a_n$ và một số nguyên dương $k$.\r\n**Yêu cầu**: Đếm xem trong đoạn $[2,k]$ có bao nhiêu số nguyên có thừa số nguyên tố nhỏ nhất là $a_i$ $(1 \\leq i \\leq n)$\r\n#### INPUT\r\n - Dòng thứ nhất chứa hai số nguyên dương $n, k$ $(1 < n \\leq 10^5, 2 \\leq k \\leq 10 ^ 6)$\r\n - Dòng thứ 2 chứa $n$ số nguyên tố $a_1,a_2,...,a_n$ $(2 \\leq a_i \\leq k, 1 \\leq i \\leq n)$.\r\n\r\n#### Output\r\n - In ra $n$ dòng với dòng thứ $i$ là số lượng số nguyên trong đoạn $[2,k]$ có thừa số nguyên tố nhỏ nhất là $a_i$.\r\n \r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"  \r\n        ```sample  \r\n        2 10\r\n        2 3\r\n        ```\r\n    ???+ success \"Output\"\r\n         ```sample  \r\n         5\r\n         2\r\n         ```\r\n    ??? warning \"Note\"\r\n        Trong đoạn $[2,10]$ có $5$ số là $2, 4, 6, 8, 10$ có thừa số nguyên tố nhỏ nhất là $2$ và có $2$ số là $3,9$ có thừa số nguyên tố nhỏ nhất là $3$.\r\n         \r\n#### Ràng buộc\r\n - Subtask $1$ ($50\\%$ số điểm): Có $n,k$ $(n, k \\leq 10^3)$\r\n - Subtask $2$ ($50\\%$ số điểm): Có $(10^3 < n \\leq 10^5, 10^3 \\leq k \\leq 10 ^ 6)$\r\n\r\n\r\n  [1]: https://lqdoj.edu.vn/organization/2083-thithuhsg","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}