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
chat gpt
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))
bài này duyệt là ok mà
ko hiểu đề.
.
bài này hơi nhiều lỗi ạ ;0;
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Cho mình hỏi là dùng đếm ước của từng số bằng công thức phân tích thừa số nt xong rồi duyệt các ước như bth so với phân tích thừa số nguyên tố kết hợp sàng eratos liệu cái nào hiệu quả hơn,mình đã nộp và thấy pt bình thường nhanh hơn
mong các bạn cho mình lời giải đáp nhé:
Code phân tích bth: https://ideone.com/77O573
Code phân tích + sàng: https://ideone.com/mOIM0Q
bài này 150p là cùng
Bai nay \(O(n^{\frac{1}{4}})\) duoc ne :))