Số nguyên tố là gì?
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số dương: 1 và chính nó. Hợp số là số có nhiều hơn hai ước số. Số 1 khá đặc biệt: nó chỉ có một ước số duy nhất, nên không phải số nguyên tố cũng chẳng phải hợp số. Công cụ này sẽ cho bạn biết số bạn nhập vào là số nguyên tố hay hợp số, liệt kê các ước số của nó, đồng thời chỉ ra số nguyên tố liền trước và liền sau.
Cách sử dụng
Nhập một số tự nhiên lớn hơn 1 vào ô và bấm tính. Công cụ sẽ phân loại đó là số nguyên tố hay hợp số, hiển thị lại con số bạn đã nhập, liệt kê toàn bộ ước số (đối với hợp số), rồi cho biết số nguyên tố lớn nhất nhỏ hơn nó và số nguyên tố nhỏ nhất lớn hơn nó.
Giải thích công thức
Chúng tôi dùng phương pháp chia thử tất định kết hợp với tối ưu hóa 6k±1. Trước hết, ta xác nhận 2 và 3 là các số nguyên tố đã biết, rồi loại bỏ ngay các số chẵn và bội của 3. Sau đó, ta chỉ kiểm tra các ước số có dạng \(6k-1\) và \(6k+1\) (5, 7, 11, 13, ...) cho đến căn bậc hai của \(n\). Nếu không có số nào chia hết \(n\) thì \(n\) là số nguyên tố. Sở dĩ chỉ cần kiểm tra đến căn bậc hai vì bất kỳ ước số nào lớn hơn căn bậc hai cũng luôn đi kèm với một ước số nhỏ hơn nó.
$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$
Ví dụ minh họa
Lấy \(n = 97\). Căn bậc hai của nó xấp xỉ 9,85. Đây là số lẻ và không phải bội của 3. Ta thử với 5 (\(97 \bmod 5 = 2\)) và 7 (\(97 \bmod 7 = 6\)). Ứng viên tiếp theo là 11, nhưng \(11 \times 11 = 121 > 97\) nên ta dừng lại. Không tìm thấy ước số nào, vậy 97 là số nguyên tố. Số nguyên tố liền trước là 89 và liền sau là 101.
Câu hỏi thường gặp
1 có phải là số nguyên tố không? Không. Số 1 chỉ có một ước số duy nhất nên không phải số nguyên tố cũng không phải hợp số.
2 có phải số nguyên tố không? Có. 2 là số nguyên tố nhỏ nhất và cũng là số nguyên tố chẵn duy nhất. Nó không có số nguyên tố nào đứng trước.
Tại sao chỉ liệt kê ước số cho hợp số? Theo định nghĩa, số nguyên tố chỉ có ước số là 1 và chính nó, nên công cụ chỉ cần ghi rõ điều đó. Hợp số có thể có nhiều ước số, chúng được liệt kê theo thứ tự tăng dần.
