LÝ THUYẾT SỐ NGUYÊN TỐ

PRIME01 - Phân loại số

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho N số nguyên không âm a1, a2, ..., aN.
Với mỗi số, hãy phân loại nó thuộc một trong ba loại:

• PRIME: số nguyên tố;
• COMPOSITE: hợp số;
• NEITHER: không phải số nguyên tố cũng không phải hợp số.

Lưu ý: 0 và 1 là NEITHER.

Dữ liệu vào

• Dòng 1 chứa số nguyên N.
• Dòng 2 chứa N số nguyên a1, a2, ..., aN.

Dữ liệu ra

In ra N dòng, dòng thứ i là kết quả phân loại của ai.

Ràng buộc

• 1 ≤ N ≤ 100
• 0 ≤ ai ≤ 10^6

Subtask

Ví dụ

Input

5
0 1 2 4 17

Output

NEITHER
NEITHER
PRIME
COMPOSITE
PRIME

PRIME02 - Kiểm tra số nguyên tố

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho một số nguyên dương n.
Hãy kiểm tra n có phải là số nguyên tố hay không.

Dữ liệu vào

Một dòng chứa số nguyên dương n.

Dữ liệu ra

• In YES nếu n là số nguyên tố.
• In NO nếu n không phải số nguyên tố.

Ràng buộc

• 1 ≤ n ≤ 10^9

Subtask

Ví dụ

Input

29

Output

YES

PRIME03 - Kiểm tra nhiều số lớn

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho Q truy vấn, mỗi truy vấn gồm một số nguyên dương n.
Với mỗi truy vấn, hãy kiểm tra n có phải số nguyên tố hay không.

Bài này yêu cầu thuật toán kiểm tra tối ưu đến √n.

Dữ liệu vào

• Dòng 1 chứa số nguyên Q.
• Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương n.

Dữ liệu ra

In ra Q dòng, mỗi dòng là:

• YES nếu n là số nguyên tố;
• NO nếu n không phải số nguyên tố.

Ràng buộc

• 1 ≤ Q ≤ 100
• 1 ≤ n ≤ 10^12

Subtask

Ví dụ

Input

4
2
10
999983
1000000

Output

YES
NO
YES
NO

PRIME04 - Liệt kê số nguyên tố bằng sàng

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho số nguyên dương N.
Hãy in ra 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.

Dữ liệu ra

In ra các số nguyên tố không vượt quá N trên một dòng, các số cách nhau một dấu cách.
Nếu không có số nguyên tố nào, in ra dòng trống.

Ràng buộc

• 1 ≤ N ≤ 10^6

Subtask

Ví dụ

Input

20

Output

2 3 5 7 11 13 17 19

PRIME05 - Đếm số nguyên tố trong đoạn

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho Q truy vấn. Mỗi truy vấn gồm hai số nguyên L, R.
Với mỗi truy vấn, hãy đếm số lượng số nguyên tố trong đoạn [L, R].

Bài này gợi ý dùng sàng Eratosthenes kết hợp mảng cộng dồn số nguyên tố.

Dữ liệu vào

• Dòng 1 chứa số nguyên Q.
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L R.

Dữ liệu ra

In ra Q dòng, dòng thứ i là số lượng số nguyên tố trong đoạn [L, R] của truy vấn thứ i.

Ràng buộc

• 1 ≤ Q ≤ 100000
• 1 ≤ L ≤ R ≤ 10^6

Subtask

Ví dụ

Input

3
1 10
10 30
90 100

Output

4
6
1

PRIME06 - Phân tích thừa số nguyên tố

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho số nguyên dương n.
Hãy phân tích n thành tích các thừa số nguyên tố.

Dữ liệu vào

Một dòng chứa số nguyên dương n.

Dữ liệu ra

• Dòng đầu in số lượng thừa số nguyên tố khác nhau.
• Các dòng tiếp theo, mỗi dòng in hai số p e, nghĩa là thừa số nguyên tố p xuất hiện với số mũ e.
• Các thừa số được in theo thứ tự tăng dần.
• Nếu n = 1, chỉ in 0.

Ràng buộc

• 1 ≤ n ≤ 10^12

Subtask

Ví dụ

Input

60

Output

3
2 2
3 1
5 1

PRIME07 - ƯCLN và BCNN bằng phân tích nguyên tố

Giới hạn

• Thời gian: 1 giây
• Bộ nhớ: 256 MB

Đề bài

Cho hai số nguyên dương A và B.
Hãy tính ƯCLN(A, B) và BCNN(A, B).

Bài toán có thể giải bằng thuật toán Euclid, nhưng trong chủ đề số nguyên tố, ta có thể phân tích A, B thành thừa số nguyên tố rồi lấy:

• ƯCLN: lấy số mũ nhỏ nhất của từng thừa số chung;
• BCNN: lấy số mũ lớn nhất của từng thừa số xuất hiện.

Dữ liệu vào

Một dòng chứa hai số nguyên dương A B.

Dữ liệu ra

In ra hai số:

UCLN BCNN

Ràng buộc

• 1 ≤ A, B ≤ 10^9
• BCNN(A, B) ≤ 10^18

Subtask

Ví dụ

Input

60 84

Output

12 420