Cho hàm
Cho hàm sau
| Đúng | Sai | |
|---|---|---|
| a) Thuật toán trên in ra các số nguyên tố nhỏ hơn n. | ||
| b) Thuật toán có độ phức tạp không gian là O(n). | ||
| c) Thuật toán sàng bắt đầu từ số nguyên tố đầu tiên là 2. | ||
| d) Trong thuật toán sàng số nguyên tố, ta thường dùng mảng kiểu boolean để đánh dấu số nào là số nguyên tố. |
Đáp án đúng là: S; Đ; Đ; Đ
Quảng cáo
Tìm số nguyên tố bằng sàng.
Độ phức tạp thời gian và không gian.
Cách sử dụng mảng boolean để đánh dấu số nguyên tố.
A Sai. Thuật toán in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n.
B Đúng.
+) Thời gian:
Duyệt các số từ 2 đến √n và đánh dấu các bội số → khoảng O(n log log n) → Đây là độ phức tạp thời gian.
+) Không gian:
Tạo mảng isPrime[0..n] để lưu trạng thái nguyên tố → O(n)
→ Đây là độ phức tạp không gian.
+) Độ phức tạp thời gian cho biết thuật toán mất bao lâu để chạy.
+) Độ phức tạp không gian cho biết thuật toán tốn bao nhiêu bộ nhớ.
+) Một thuật toán tốt nên cân bằng cả hai yếu tố này.
C Đúng. Thuật toán sàng Eratosthenes khởi đầu với giả định rằng tất cả các số từ 2 đến n đều là số nguyên tố.
+) Quá trình sàng bắt đầu từ số 2, là số nguyên tố đầu tiên.
+) Các bội số của 2 (như 4, 6, 8,...) sẽ bị loại bỏ (đánh dấu là không nguyên tố).
+) Sau đó thuật toán tiếp tục với số tiếp theo chưa bị loại, ví dụ 3, rồi 5, 7, v.v.
D Đúng. Cách làm phổ biến là sử dụng một mảng kiểu boolean (đúng/sai):
+) Ban đầu, tất cả các phần tử trong mảng isPrime[0..n] được gán là True .
+) Khi tìm thấy một số là bội số của một số nguyên tố, ta gán giá trị False cho chỉ số đó – tức là không phải số nguyên tố.
+) Cuối cùng, chỉ các chỉ số còn giữ giá trị True mới là các số nguyên tố.
Đáp án cần chọn là: S; Đ; Đ; Đ
Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí
>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
