Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
knto.inp
Output:
knto.out
Ngôn ngữ cho phép
C++, PyPy, Python
Số không nguyên tố (hợp số): Là số tự nhiên lớn hơn 1 và có nhiều hơn hai ước số dương.
- Hay nói cách khác, ngoài 1 và chính nó, số đó còn chia hết cho ít nhất một số tự nhiên khác.
Ví dụ:
- ~4~ là hợp số vì nó có các ước số: ~{1, 2, 4}~.
- ~6~ là hợp số vì nó có các ước số: ~{1, 2, 3, 6}~.
Yêu cầu:
Cho một số nguyên dương ~n~, xét ~P~ là tập hợp các ước số dương không nguyên tố của ~n~.
Hãy tìm số phần tử của tập hợp ~P~.
Input (KNTO.INP
):
- Gồm 1 dòng duy nhất chứa số nguyên dương ~n~ (~1 \leq n \leq 10^{14}~)
Ouput (KNTO.OUT
):
- Ghi ra 1 số nguyên duy nhất, là số phần tử của tập hợp ~P~.
Sample
KNTO.INP
180
KNTO.OUT
15
Giải thích:
- Ước số của ~180~: ~{1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}~
- Các ước số không nguyên tố: ~{1, 4, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}~
- Kết quả: ~15~
KNTO.INP
20
KNTO.OUT
4
Ràng buộc:
- 40% số test đầu tiên: ~ n \leq 10^6 ~
- 60% số test còn lại: ~ n \leq 10^{14} ~
Bình luận