python-058Đọc toàn bộ đề miễn phí
Sàng nguyên tố Eratosthenes và Phân tích thừa số nguyên tố
Viết hàm sieve_and_prime_factorization(n: int) -> tuple[list[int], dict[int, int]]:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: loops, dictionaries.
Nội dung đề bài
Mục tiêu kiến thức
- Triển khai sàng nguyên tố Eratosthenes tối ưu O(N log log N).
- Phân tích một số nguyên dương thành tích các thừa số nguyên tố kèm số mũ p1e1 · p2e2 …
- Xử lý ngoại lệ đầu vào với
ValueErrorkhi tham số không hợp lệ.
Mô tả bài toán
Viết hàm sieve_and_prime_factorization(n: int) -> tuple[list[int], dict[int, int]]:
- Kiểm tra tham số n: nếu n < 1, raise
ValueError("n phai la so nguyen duong"). - Tạo danh sách tất cả các số nguyên tố ≤ n (theo thứ tự tăng dần). Nếu n < 2, danh sách là
[]. - Phân tích n thành thừa số nguyên tố dưới dạng
dict[int, int]trong đó key là số nguyên tố và value là số mũ (ví dụ 12 → {2: 2, 3: 1}). Với n = 1, trả về{}.
Input
- Tham số:
n: int.
Output
- Trả về:
tuple[list[int], dict[int, int]]. - Ngoại lệ:
ValueErrorkhi n < 1.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
sieve_and_prime_factorization(12)Output
[[2, 3, 5, 7, 11], {'2': 2, '3': 1}]Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
sieve_and_prime_factorization(1)Output
[[], {}]Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.