Một số được gọi là "Tự Do Bình Phương" nếu nó không chia hết cho bất kỳ bình phương của một số nguyên tố nào. Ví dụ: 10 (tự do) vì 10 = 2 x 5. 12 (không) vì 12 chia hết cho 2^2=4. Cho N. Hãy đếm số lượng số Tự Do Bình Phương i (1 <= i <= N). (Số 1 được tính là 1 số).

Input:

Một dòng duy nhất chứa số nguyên N (1 <= N <= 1000000).

Output:

In ra số lượng số Tự Do Bình Phương.

Test Case 1:

Input:

20

Output:

13

(Giải thích: Các số bị loại (chia hết cho 4, 9, 16...): {4, 8, 9, 12, 16, 18, 20}. 20 - 7 = 13)

Cho T truy vấn. Với mỗi số X, hãy in ra phân tích thừa số nguyên tố của X dưới dạng p1^a1 x p2^a2 x ... Yêu cầu: Dùng Sàng để tìm Ước SNT Nhỏ Nhất (SPF - Smallest Prime Factor) để tăng tốc độ phân tích.

Input:

Dòng đầu tiên chứa T (1 <= T <= 100000).

T dòng tiếp theo, mỗi dòng chứa một số nguyên X (2 <= X <= 1000000).

Output:

T dòng, mỗi dòng là chuỗi phân tích. (Xem ví dụ).

Test Case 1:

Input:

3
12
13
28

Output:

2^2 x 3^1
13^1
2^2 x 7^1

Cho T truy vấn. Với mỗi số X, hãy in ra tất cả các thừa số nguyên tố của X (bao gồm cả lặp lại). Ví dụ: 12 -> 2 2 3.

Input:

Dòng đầu tiên chứa T (1 <= T <= 100000).

T dòng tiếp theo, mỗi dòng chứa một số nguyên X (2 <= X <= 1000000).

Output:

T dòng, mỗi dòng là danh sách các thừa số nguyên tố, cách nhau bởi dấu cách.

Test Case 1:

Input:

3
30
12
17

Output:

2 3 5
2 2 3
17

Cho một mảng A gồm K phần tử. Hãy đếm xem có bao nhiêu số nguyên tố xuất hiện trong mảng A.

Input:

Dòng đầu tiên chứa số nguyên K (1 <= K <= 100000).

Dòng thứ hai chứa K số nguyên Ai (1 <= Ai <= 1000000), cách nhau bởi dấu cách.

Output:

In ra số lượng số nguyên tố trong mảng A.

Test Case 1:

Input:

5
4 7 10 11 13

Output:

3

(Giải thích: Các SNT là {7, 11, 13})

Cho N. Tìm số i (1 <= i <= N) có số lượng ước số lớn nhất. Nếu có nhiều số i có cùng số lượng ước lớn nhất, hãy in ra số i nhỏ nhất. Gợi ý: Nếu n = p1^a1 x p2^a2, thì d(n) = (a1+1) x (a2+1).

Input:

Một dòng duy nhất chứa số nguyên N (1 <= N <= 100000).

Output:

In ra số i có nhiều ước nhất.

Test Case 1:

Input:

10

Output:

6

(Giải thích: 6, 8, 10 đều có 4 ước. Chọn 6 vì nhỏ nhất)

Cho một số nguyên N. Tìm số nguyên tố p nhỏ nhất sao cho p > N.

Input:

Một dòng duy nhất chứa số nguyên N (1 <= N <= 1000000).

Output:

In ra số nguyên tố p nhỏ nhất lớn hơn N. (Lưu ý: Sàng phải được xây dựng đến N + k nào đó đủ lớn. Với N=1000000, SNT tiếp theo là 1000003)

Test Case 1:

Input:

15

Output:

17

Cho N và Q truy vấn [L, R]. Hãy tính tổng các số nguyên tố trong đoạn [L, R]. Yêu cầu: Xây dựng Sàng, sau đó dùng Mảng Cộng Dồn (Prefix Sum) để lưu tổng các SNT.

Input:

Dòng đầu tiên chứa hai số nguyên N và Q (1 <= N <= 1000000, 1 <= Q <= 100000).

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 <= L <= R <= N).

Output:

In ra Q dòng, mỗi dòng là tổng các SNT trong đoạn [L, R]. (Dùng long long).

Test Case 1:

Input:

15 2
1 7
10 15

Output:

17
24

(Giải thích 1: S[7] - S[0] = 17 - 0 = 17. Giải thích 2: S[15] - S[9] = 41 - 17 = 24)

Cho một số nguyên N. Tìm tích lớn nhất P = p x q sao cho p và q là hai số nguyên tố (có thể p=q) và P <= N.

Input:

Một dòng duy nhất chứa số nguyên N (4 <= N <= 1000000).

Output:

In ra tích P lớn nhất.

Test Case 1:

Input:

20

Output:

15

(Giải thích: Các tích: 4, 6, 9, 10, 14, 15. Lớn nhất là 15 = 3 x 5)