Số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
1,23 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Số nguyên tố là số chỉ chia hết cho ~1~ và chính nó. Trong một buổi dã ngoại của trường, bất ngờ TMB bị thầy giáo đố một câu như sau: "Một số có dạng ~p^{q}~ là lũy thừa cao của một số nguyên tố khi và chỉ khi ~p~ là một số nguyên tố và ~q > 1~. Thầy sẽ cho em một số ~N~ bất kỳ và em hãy cho biết đó có phải là lũy thừa cao của một số nguyên tố hay không? ". Không phải lúc nào cũng mang theo máy tính bên mình, đây là lúc TMB cần bạn.
Yêu cầu: Cho số ~N~, hãy giúp TMB trả lời câu đố của thầy giáo, nếu ~N~ là lũy thừa cao của một số nguyên tố thì in ra ~2~ số ~p~ và ~q~ tương ứng, nếu không thì ghi ~0~.
Input
- ~1~ dòng duy nhất chứa ~n~
Output
- ~1~ dòng duy nhất là kết quả
Giới hạn
~n \le 10^{18}~
Sample Input 1
27
Sample Output 1
3 3
Sample Input 2
10
Sample Output 2
0
Bình luận
spidi spidu
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Spoil thuật không miller rabin
Unofficial Solution