Số bốn ước
Xem PDF
Điểm:
300
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho \(1\) số nguyên dương \(n\), đếm xem \(n\) có bao nhiêu ước dương sao cho ước đó có đúng \(4\) ước nguyên dương.
Input
- Một dòng duy nhất là số \(n\).
Output
- \(1\) số duy nhất là kết quả.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^4\).
- Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^6\).
Example
Test 1
Input
8Output
1Note
Chỉ có \(1\) ước thỏa mãn là \(8\).
Bình luận
def count_divisors(x):
""" Tính số lượng ước của số x """
count = 0
sqrt_x = int(x**0.5)
for i in range(1, sqrt_x + 1):
if x % i == 0:
if i * i == x:
count += 1
else:
count += 2
return count
def find_divisors(n):
""" Tìm tất cả các ước số của n """
divisors = set()
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.add(i)
divisors.add(n // i)
return divisors
def count_divisors_with_four_divisors(n):
""" Đếm số lượng ước số của n mà có đúng 4 ước số """
count = 0
divisors = find_divisors(n)
for d in divisors:
if count_divisors(d) == 4:
count += 1
return count
Đọc đầu vào
n = int(input().strip())
Tính và in ra kết quả
print(count_divisors_with_four_divisors(n))
9 bình luận nữa