Đề

Dùng hàm la_nguyen_to(n) của Ví dụ 5.1 (mục 5.5.1), viết thêm hàm dem_nguyen_to(a, b) trả về số lượng số nguyên tố trong đoạn ~[a; b]~ (tính cả hai đầu ~a~ và ~b~). Chương trình chính đọc ~a~, ~b~ và in số lượng.

Nhắc lại: số nguyên tố là số nguyên lớn hơn 1 chỉ có hai ước dương là 1 và chính nó (2, 3, 5, 7, 11, …). Số 0, số 1 và mọi số âm không là số nguyên tố.

Dữ liệu vào

Một dòng chứa hai số nguyên ~a~ và ~b~ (~a \le b~), cách nhau một dấu cách.

Kết quả

Một dòng: số lượng số nguyên tố ~n~ với ~a \le n \le b~.

Ràng buộc

• ~-10^6 \le a \le b \le 10^6~.
• ~b - a \le 10\,000~ (đoạn có không quá 10 001 số).

Ví dụ

Dữ liệu vào:

50 70

Kết quả:

4

Giải thích ví dụ

Trong đoạn ~[50; 70]~ có bốn số nguyên tố: 53, 59, 61, 67. Các số còn lại đều có ước nhỏ: ví dụ 51 = 3 × 17, 57 = 3 × 19, 63 = 7 × 9, 69 = 3 × 23.

Hàm dem_nguyen_to chỉ cần một vòng for n in range(a, b + 1) gọi la_nguyen_to(n) và đếm; biến đếm là biến cục bộ của hàm, trả ra bằng return (mục 5.4).

Ghi chú

• Đoạn có thể chứa 0, 1 và số âm: hàm la_nguyen_to phải trả False cho mọi ~n < 2~.
• Lệnh return True của la_nguyen_to nằm sau vòng lặp; đặt vào nhánh else trong vòng lặp thì 9, 15 bị coi là nguyên tố (mục 5.5.1).
• Chỉ cần thử ước tới căn bậc hai (uoc * uoc <= n, mục 4.6.1). Thử mọi ước từ 2 đến ~n - 1~ vẫn đúng nhưng với các số gần ~10^6~ thì quá chậm: test lớn bị Time Limit.
• Hệ thống chỉ so kết quả in ra; yêu cầu "dùng lại la_nguyen_to, có ít nhất ba assert" là phần giảng viên kiểm khi chấm tay.

Nguồn trong sách: Bài C5-05, mục 5.10, giáo trình "Lập trình cơ sở với Python" — TS. Nguyễn Quốc Long · Mức: (**)