Cho số nguyên dương n.
Yêu cầu: Kiểm tra xem n có phải là số nguyên tố hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1012).
Dữ liệu ra: In YES nếu n là số nguyên tố, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 29 | YES | 29 chỉ có đúng hai ước dương là 1 và 29. |
Giới hạn:
Ghi chú: Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước dương là 1 và chính nó.
Cho hai số nguyên dương a và b (a ≤ b).
Yêu cầu: Đếm có bao nhiêu số nguyên tố thuộc đoạn [a, b].
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a ≤ b ≤ 106).
Dữ liệu ra: In số lượng số nguyên tố trong đoạn.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 10 20 | 4 | Các số nguyên tố là 11, 13, 17 và 19. |
Giới hạn:
Cho hai số nguyên dương a và b (a ≤ b).
Yêu cầu: Tính tổng các số nguyên tố thuộc đoạn [a, b].
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a ≤ b ≤ 106).
Dữ liệu ra: In tổng các số nguyên tố trong đoạn.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 2 10 | 17 | Các số nguyên tố là 2, 3, 5, 7. |
Giới hạn:
Cho hai số nguyên dương a và b (a ≤ b).
Yêu cầu: Tìm số nguyên tố lớn nhất thuộc đoạn [a, b]. Nếu không tồn tại, in -1.
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a ≤ b ≤ 106).
Dữ liệu ra: In kết quả bài toán.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 20 40 | 37 | 37 là số nguyên tố lớn nhất trong đoạn. |
Giới hạn:
Cho hai số nguyên dương a và b (a ≤ b).
Yêu cầu: Tìm số nguyên tố nhỏ nhất thuộc đoạn [a, b]. Nếu không tồn tại, in -1.
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a ≤ b ≤ 106).
Dữ liệu ra: In kết quả bài toán.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 20 40 | 23 | 23 là số nguyên tố nhỏ nhất trong đoạn. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Liệt kê tất cả các số nguyên tố không vượt quá n theo thứ tự tăng dần.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 107).
Dữ liệu ra: In các số nguyên tố không vượt quá n, cách nhau một dấu cách.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 20 | 2 3 5 7 11 13 17 19 | Đây là các số nguyên tố không vượt quá 20. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Đếm số lượng số nguyên tố không vượt quá n.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 107).
Dữ liệu ra: In số lượng số nguyên tố không vượt quá n.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 20 | 8 | Có 8 số nguyên tố không vượt quá 20. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Tính tổng các số nguyên tố không vượt quá n.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 107).
Dữ liệu ra: In tổng các số nguyên tố không vượt quá n.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 10 | 17 | 2 + 3 + 5 + 7 = 17. |
Giới hạn:
Cho q truy vấn, mỗi truy vấn gồm một số nguyên dương n.
Yêu cầu: Với mỗi truy vấn, kiểm tra n có phải là số nguyên tố hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Dòng đầu chứa số nguyên q (1 ≤ q ≤ 105). Mỗi dòng tiếp theo chứa một số nguyên dương n (n ≤ 107).
Dữ liệu ra: Với mỗi truy vấn in một dòng kết quả.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 3 2 10 13 |
YES NO YES |
Giới hạn:
Cho số nguyên dương k.
Yêu cầu: Tìm số nguyên tố thứ k.
Dữ liệu vào: Một dòng chứa số nguyên dương k (1 ≤ k ≤ 5×105).
Dữ liệu ra: In số nguyên tố thứ k.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 6 | 13 | Dãy số nguyên tố bắt đầu là 2, 3, 5, 7, 11, 13,... nên số nguyên tố thứ 6 là 13. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Phân tích n thành tích các thừa số nguyên tố theo thứ tự tăng dần.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In các thừa số nguyên tố của n theo dạng p^k, các thừa số cách nhau bởi dấu *.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 360 | 2^3 * 3^2 * 5^1 | 360 = 2×2×2×3×3×5. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Đếm tổng số lượng thừa số nguyên tố của n (tính cả số lần lặp).
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In số lượng thừa số nguyên tố.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 360 | 6 | 360 = 2×2×2×3×3×5 nên có 6 thừa số nguyên tố. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Đếm số lượng thừa số nguyên tố khác nhau của n.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In kết quả bài toán.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 360 | 3 | Các thừa số nguyên tố khác nhau là 2, 3 và 5. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Tìm thừa số nguyên tố lớn nhất của n.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In thừa số nguyên tố lớn nhất của n.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 360 | 5 | 5 là thừa số nguyên tố lớn nhất của 360. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Tìm thừa số nguyên tố nhỏ nhất của n.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In thừa số nguyên tố nhỏ nhất của n.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 360 | 2 | 2 là thừa số nguyên tố nhỏ nhất của 360. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Kiểm tra n có phải là số chính phương hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 144 | YES | 144 = 12 × 12. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Kiểm tra n có phải là số lập phương hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1018).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 343 | YES | 343 = 7 × 7 × 7. |
Giới hạn:
Cho hai số nguyên dương a và b.
Yêu cầu: Kiểm tra xem a và b có cùng tập các thừa số nguyên tố hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a, b ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 12 18 | YES | 12 = 2² × 3, 18 = 2 × 3² nên cùng có các thừa số nguyên tố là 2 và 3. |
Giới hạn:
Cho hai số nguyên dương n và k.
Yêu cầu: Đếm có bao nhiêu số trong đoạn từ 2 đến n có đúng k thừa số nguyên tố khác nhau.
Dữ liệu vào: Một dòng chứa hai số nguyên dương n và k (2 ≤ n ≤ 106).
Dữ liệu ra: In kết quả bài toán.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 10 2 | 2 | Hai số là 6 và 10. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Kiểm tra n có phải là số bán nguyên tố hay không. Một số được gọi là bán nguyên tố nếu nó là tích của đúng hai số nguyên tố (hai số nguyên tố có thể trùng nhau). Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 15 | YES | 15 = 3 × 5 nên là số bán nguyên tố. |
Giới hạn:
Ghi chú: Số bán nguyên tố là số có đúng hai thừa số nguyên tố (tính cả trường hợp hai thừa số giống nhau, ví dụ: 9 = 3 × 3).
Cho số nguyên dương n.
Yêu cầu: Kiểm tra xem n có phải là số chính phương hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 144 | YES | 144 = 12 × 12 nên là số chính phương. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Kiểm tra xem n có phải là số lập phương hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1018).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 343 | YES | 343 = 7 × 7 × 7. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Kiểm tra xem n có phải là số hoàn hảo hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 28 | YES | 28 = 1 + 2 + 4 + 7 + 14. |
Giới hạn:
Ghi chú: Số hoàn hảo là số có tổng các ước dương (không kể chính nó) bằng chính số đó.
Cho số nguyên dương n.
Yêu cầu: Kiểm tra xem n có phải là số mạnh hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa số nguyên dương n (1 ≤ n ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 72 | YES | 72 = 2³ × 3², mọi thừa số nguyên tố đều có số mũ lớn hơn hoặc bằng 2. |
Giới hạn:
Ghi chú: Số mạnh là số mà trong phân tích thừa số nguyên tố, mọi thừa số nguyên tố đều có số mũ lớn hơn hoặc bằng 2.
Cho hai số nguyên dương a và b.
Yêu cầu: Kiểm tra xem a và b có cùng tập các thừa số nguyên tố hay không. Nếu đúng in YES, ngược lại in NO.
Dữ liệu vào: Một dòng chứa hai số nguyên dương a và b (1 ≤ a, b ≤ 1012).
Dữ liệu ra: In YES hoặc NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 12 18 | YES | 12 = 2² × 3, 18 = 2 × 3² nên cùng có tập thừa số nguyên tố là {2, 3}. |
Giới hạn:
Cho số nguyên dương n.
Yêu cầu: Phân tích n! thành tích các thừa số nguyên tố theo dạng p^k.
Dữ liệu vào: Một dòng chứa số nguyên dương n (2 ≤ n ≤ 1000).
Dữ liệu ra: In kết quả theo thứ tự tăng dần của các thừa số nguyên tố, mỗi thừa số có dạng p^k, các thừa số cách nhau bởi dấu *.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 10 | 2^8 * 3^4 * 5^2 * 7 | 10! = 1 × 2 × 3 × ... × 10 = 28 × 34 × 52 × 7. |
Giới hạn:
Gợi ý: Có thể phân tích lần lượt các số từ 2 đến n rồi cộng số mũ của từng thừa số nguyên tố. Không bắt buộc sử dụng công thức Legendre.
Cho dãy gồm n số nguyên dương a1, a2, ..., an.
Yêu cầu: Phân tích tích a1 × a2 × ... × an thành tích các thừa số nguyên tố theo dạng p^k.
Dữ liệu vào: Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 104). Dòng thứ hai chứa n số nguyên dương ai (2 ≤ ai ≤ 106).
Dữ liệu ra: In kết quả theo thứ tự tăng dần của các thừa số nguyên tố, mỗi thừa số có dạng p^k, các thừa số cách nhau bởi dấu *.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 3 12 18 25 |
2^3 * 3^3 * 5^2 | 12 × 18 × 25 = 23 × 33 × 52. |
Giới hạn:
Gợi ý: Phân tích từng số trong dãy thành các thừa số nguyên tố, sau đó cộng số mũ của từng thừa số bằng map hoặc unordered_map.