Thừa số nguyên tố nhỏ nhất

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

JOIN TỔ CHỨC ĐỂ THAM GIA CÁC KÌ THI THỬ HSG 8,9 Bấm vào đây
Vớ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.
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\).
Cho 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\).
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)\)

INPUT

  • 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)\)
  • 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)\).

Output

  • 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\).

Example

Test 1

Input
2 10
2 3
Output
5
2
Note

Trong đoạn \([2,10]\)\(5\) số là \(2, 4, 6, 7, 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àng buộc

  • Subtask \(1\) (\(50\%\) số điểm): Có \(n,k\) \((n, k \leq 10^3)\)
  • Subtask \(2\) (\(50\%\) số điểm): Có \((10^3 < n \leq 10^5, 10^3 \leq k \leq 10 ^ 6)\)

Bình luận

Không có bình luận nào.