Sàng đếm ước và sàng đếm số NT
Phân tích thừa số nguyên tố nhanh (Fast factorization)
Nộp bàiPoint: 1
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
Số lượng ước nguyên tố khác nhau
Nộp bàiPoint: 1
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
Cặp số thân thiết (Amicable numbers)
Nộp bàiPoint: 1
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)
Số có nhiều ước nhất trong đoạn
Nộp bàiPoint: 1
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
Nộp bàiPoint: 1
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
Số lượng ước là số nguyên tố
Nộp bàiPoint: 1
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