Problem ID:
ts10kh_23_4
Points:
1.6 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
zfactor.inp
Output:
zfactor.out
Author:
Problem type
Với một số nguyên ~P~ ~(P \ge 2)~, ta có thể phân tích ~P~ thành tích của 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ì số ~2~ là thừa số nguyên tố nhỏ nhất của ~100~; ~15 = 3 \times 5~ thì số ~3~ là thừa số nguyên tố nhỏ nhất của ~15~.
Cho trước một dãy ~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~.
Dữ liệu vào
- Từ tệp văn bản
ZFACTOR.INP
gồm:- Dòng đầu tiên ghi ~2~ số nguyên dương ~n~ và ~k~ ~(n \le 10^5, 2 \le k \le 10^6)~.
- Dòng thứ hai ghi ~n~ số nguyên tố ~a_1, a_2, ... , a_n~ trên cùng một dòng và giữa các số cách nhau bởi một dấu cách ~(2 \le a_i \le k, 1 \le i \le n)~.
Kết quả
- Ghi vào tệp văn bản
ZFACTOR.OUT
gồm ~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~.
Giới hạn
- Có ~50\%~ test với ~n \le 10^3~, ~k \le 10^3~.
- Có ~50\%~ test với ~10^3 < n \le 10^5, 10^3 < k \le 10^6~.
Ví dụ
Dữ liệu
2 10
2 3
Kết quả
5
2
Giải thích
- 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~ và ~9~ có thừa số nguyên tố nhỏ nhất là ~3~.
Comments