Công cụ này làm được gì
Đây là công cụ số nguyên tố ba-trong-một. Nó có thể (1) tìm số nguyên tố thứ n, ký hiệu \(\text{Prime}[n] = p_n\); (2) kiểm tra một số nguyên cho trước có phải là số nguyên tố hay không và cho biết vị trí của nó trong dãy số nguyên tố; và (3) liệt kê N số nguyên tố đầu tiên theo yêu cầu. Những số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, ... Số nguyên tố là số nguyên lớn hơn 1 mà chỉ chia hết cho 1 và cho chính nó.
Cách sử dụng
Hãy chọn một chế độ. Ở chế độ Số nguyên tố thứ n, bạn nhập vị trí n (đánh số từ 1, ví dụ 100) và công cụ trả về \(\text{Prime}[100] = 541\). Ở chế độ Kiểm tra tính nguyên tố, bạn nhập một số nguyên bất kỳ (ví dụ 97) và công cụ cho biết số đó có phải số nguyên tố không, nếu có thì kèm chỉ số n của nó trong dãy. Ở chế độ Liệt kê N số nguyên tố đầu tiên, bạn nhập số lượng cần lấy và công cụ trả về danh sách đầy đủ, cách nhau bằng dấu phẩy, cùng với số nguyên tố lớn nhất là \(\text{Prime}[N]\).
Giải thích công thức
Phép kiểm tra tính nguyên tố dựa trên phương pháp chia thử: một số p là số nguyên tố khi không tồn tại ước số nguyên nào nằm giữa 2 và căn bậc hai của p. Sau khi xử lý số 2, ta chỉ cần thử các ước lẻ d trong khi \(d \cdot d \le p\) — cách này nhanh và tránh được sai số dấu phẩy động.
$$\text{N} \text{ is prime} \iff \text{N} \ge 2 \;\wedge\; \nexists\, d \in \left[2,\;\sqrt{\text{N}}\,\right]: d \mid \text{N}$$Để tìm số nguyên tố thứ n, ta quét lần lượt các số 2, 3, 4, ... và đếm từng số nguyên tố cho đến khi đạt đúng n. Chỉ số nguyên tố của một số nguyên tố m chính bằng \(\pi(m)\), tức số lượng số nguyên tố nhỏ hơn hoặc bằng m.
Ví dụ minh họa
Kiểm tra số 97. Đây là số lẻ, nên ta thử \(d = 3, 5, 7, 9\) (vì \(9^2 = 81 \le 97\) nhưng \(11^2 = 121 > 97\)). Không có số nào chia hết 97, vậy 97 là số nguyên tố. Đếm các số nguyên tố tính đến 97 gồm 2, 3, 5, ..., 97 cho ra 25 số, nên 97 là số nguyên tố thứ 25: \(\text{primeIndex} = 25\).
Câu hỏi thường gặp
Số 1 có phải là số nguyên tố không? Không. Theo định nghĩa, số nguyên tố phải lớn hơn 1, vì vậy 1 không phải số nguyên tố cũng không phải hợp số.
Số nguyên tố chẵn duy nhất là số nào? Đó là số 2 — số nguyên tố chẵn duy nhất; mọi số chẵn khác đều chia hết cho 2.
Số nguyên tố thứ 100 là số nào? \(\text{Prime}[100] = 541\). Một vài mốc khác: \(\text{Prime}[10] = 29\), \(\text{Prime}[25] = 97\), \(\text{Prime}[50] = 229\), \(\text{Prime}[223] = 1409\).
