Cho số nguyên dương N ≤ 10^6.

Với mỗi số nguyên dương i (1 ≤ i ≤ N), hãy đếm:

1. Số ước chẵn của i.

2. Số ước lẻ của i.

3. Số ước của i mà bản thân ước đó là số nguyên tố.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra:

In ra N dòng, mỗi dòng chứa 3 số nguyên, cách nhau bởi một dấu cách

evencount[i] oddcount[i] prime_count[i]

trong đó:

• even_count [il là số ước chẵn của i,

• odd_count [il là số ước lẻ của i,

• prime_count [il là số ước nguyên tố của i.

Ví dụ:

Input 01:

6

Output 01:

0 1 0
1 1 1
0 2 1
2 1 1
0 2 1
2 2 2

Cho một số nguyên dương N ≤ 10^6.

Hãy tìm tất cả các số trong đoạn [1..N] có số lượng ước nhiều nhất.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra:

• Dòng đầu tiên: in số lượng ước lớn nhất.

• Dòng thứ hai: in các số trong đoạn [1..N] có đúng số lượng ước đó, theo thứ tự tăng dần, cách nhau bởi một dấu cách.

Input 01:

6

Output 01:

4
6

Input 02:

10

Output 02:

4
6 8 10

Giải thích: Các số 6, 8, 10 là các số có số lượng ước lớn nhất (=4) trong khoảng từ 1 đến 10

Cho Q truy vấn, mỗi truy vấn là một số n. Hãy đếm xem n có bao nhiêu ước số nguyên tố khác nhau. Ví dụ 12 = 2^2 * 3^1 có 2 ước nguyên tố khác nhau là 2 và 3.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau, mỗi dòng chứa n.

Dữ liệu ra: Q dòng, mỗi dòng là số lượng ước nguyên tố khác nhau.

Ràng buộc: 1 <= Q <= 100000; 1 <= n <= 1000000

Ví dụ 1:

Input:

3 
12 
30 
7

Output:

2 
3 
1

Ví dụ 2:

Input:

2 1 100

Output:

0 2

Sử dụng kỹ thuật sàng để phân tích thừa số nguyên tố cho Q số nguyên n. Với mỗi số, in ra các thừa số nguyên tố theo thứ tự tăng dần.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau, mỗi dòng chứa n.

Dữ liệu ra: Q dòng, mỗi dòng chứa các thừa số nguyên tố của n cách nhau bởi dấu cách.

Ràng buộc: 1 <= Q <= 100000; 2 <= n <= 1000000

Ví dụ 1:

Input:

2 
12 
10

Output:

2 2 3 
2 5

Ví dụ 2:

Input:

2 
7 
18

Output:

7 
2 3 3

Hai số a và b được gọi là cặp số thân thiết nếu tổng các ước thực sự (không tính chính nó) của a bằng b và ngược lại. Hãy liệt kê tất cả các cặp số thân thiết (a, b) sao cho a < b <= N cho trước.

Dữ liệu vào: Dòng duy nhất chứa số N.

Dữ liệu ra: Mỗi dòng in một cặp số a b cách nhau bởi dấu cách.

Ràng buộc: 1 <= N <= 100000

Ví dụ 1:

Input:

300

Output:

220 284

Ví dụ 2:

Input:

100

Output:

(Không có đầu ra)

Cho số nguyên N. Tìm số nguyên dương x <= N sao cho số lượng ước số của x là lớn nhất. Nếu có nhiều số, in ra số nhỏ nhất.

Dữ liệu vào: Dòng duy nhất chứa số N.

Dữ liệu ra: In ra số x tìm được.

Ràng buộc: 1 <= N <= 100000

Ví dụ 1:

Input:

10

Output:

6

Ví dụ 2:

Input:

20

Output:

12

Số Sphenic là số nguyên dương là tích của đúng 3 số nguyên tố khác nhau. Cho Q truy vấn, kiểm tra xem n có phải số Sphenic không.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: In 1 nếu là Sphenic, 0 nếu không.

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

3 30 42 60

Output:

1 1 0

Ví dụ 2:

Input:

2 8 1

Output:

0 0

Cho Q truy vấn n. Hãy đếm xem trong các ước số của n, có bao nhiêu số là số nguyên tố.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: Q dòng kết quả.

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

2 
10 
12

Output:

2 2

Ví dụ 2:

Input:

2 7 30

Output:

1 3

Số thịnh vượng (Abundant Number) là một số nguyên dương mà tổng các ước số thực sự của nó (các ước nhỏ hơn chính nó) lớn hơn chính nó.

Ví dụ:

Số 12 có các ước số thực sự là 1, 2, 3, 4, 6. Tổng các ước là 1 + 2 + 3 + 4 + 6 = 16. Vì 16 > 12 nên 12 là số thịnh vượng.

Số 10 có các ước số thực sự là 1, 2, 5. Tổng các ước là 1 + 2 + 5 = 8. Vì 8 < 10 nên 10 không phải là số thịnh vượng.

Cho Q câu hỏi, mỗi câu hỏi gồm một số nguyên N. Hãy kiểm tra xem N có phải là số thịnh vượng hay không.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên Q là số lượng truy vấn.

Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương N cần kiểm tra.

Dữ liệu ra:

Với mỗi giá trị N, in ra "YES" nếu N là số thịnh vượng, in ra "NO" nếu không phải. (Mỗi kết quả trên một dòng).

Giới hạn:

1 <= Q <= 10^6

1 <= N <= 10^6

Thời gian chạy: 1 giây

Ví dụ:

Input:

3 
12 
10 
18

Output:

YES 
NO 
YES

Số Blum là số nguyên dương n = p * q, trong đó p và q là hai số nguyên tố khác nhau và cả hai đều chia 4 dư 3. Cho Q truy vấn, kiểm tra n có phải số Blum không.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: In 1 nếu là Blum, 0 nếu không.

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

3 
21 
33 
9

Output:

1 
1 
0

Ví dụ 2:

Input:

2 
5 
7

Output:

0 
0

Cho Q truy vấn n. Kiểm tra xem tổng các ước số của n có phải là số nguyên tố hay không.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: In "YES" hoặc "NO".

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

3 
2 
4 
6

Output:

YES 
YES 
NO