Mô tả
Bảo tàng Dân tộc học Hà Nội đang rà soát lại kho dự trữ với hàng nghìn thùng artifact. Để chống trùng lặp phân loại, ban quản lý quyết định gán cho mỗi thùng một mã phụ đặc biệt: ước nguyên tố nhỏ nhất của mã số thùng đó.
Ví dụ, thùng mang mã số 15 được phân tích thành 3 × 5, vậy mã phụ là 3 — viên gạch nền tảng nhỏ nhất cấu thành nên 15. Thùng mã số 17 (bản thân đã là số nguyên tố) nhận mã phụ là chính nó.
Nhiều thùng cũ đã hỏng nhãn, mã số bị mờ hoặc vô tình ghi sai thành những giá trị không hợp lệ (0, 1, hoặc số âm). Những thùng này cần được đánh dấu mã phụ là -1 để nhân viên tách riêng kiểm tra thủ công.
Nhiệm vụ của bạn: cho trước mã số thùng N, hãy xác định mã phụ — ước nguyên tố nhỏ nhất của N, hoặc -1 nếu N không hợp lệ.
Đầu vào
Một số nguyên duy nhất N (kiểu số nguyên).
Đầu ra
Trả về một số nguyên: ước nguyên tố nhỏ nhất của N nếu N ≥ 2, hoặc -1 nếu N ≤ 1.
Ràng buộc
- -10⁹ ≤ N ≤ 10⁹
- Đảm bảo mọi giá trị trung gian không vượt quá 10¹⁸, an toàn với số nguyên 64-bit.
Ví dụ
Ví dụ 1:
- Đầu vào:
15 - Đầu ra:
3 - Giải thích: 15 = 3 × 5. Thừa số nguyên tố nhỏ nhất là 3, vậy mã phụ của thùng là 3.
Ví dụ 2:
- Đầu vào:
17 - Đầu ra:
17 - Giải thích: 17 là số nguyên tố, không phân tích được tiếp. Mã phụ chính là 17.
Ví dụ 3:
- Đầu vào:
1