Số không nguyên tố

Xem dạng PDF

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.