Câu hỏi 109
Tất cả các ước số dương của số nguyên dương $n$ được lưu trữ vào một mảng theo thứ tự tăng dần. Mary phải viết một chương trình quyết định số chia được chọn tùy ý $d\gt 1$ xem nó có phải là số nguyên tố hay không. Giả sử $n$ có ước số $k$ không lớn hơn $d$. Mary tuyên bố rằng chỉ cần kiểm tra tính chia hết của $d$ cho các ước số $\lceil k / 2\rceil$ đầu tiên của $n$: Nếu tìm thấy một ước số của $d$ lớn hơn 1 trong số chúng, thì $d$ là hợp số, nếu không thì $d$ là số nguyên tố. Mary có đúng không?