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\).
Bảng số nguyên tố: 25 số nguyên tố đầu tiên và các mốc chỉ số
Chỉ số \(n\) là vị trí của một số nguyên tố trong dãy số nguyên tố tăng dần, nên \(p_n\) là số nguyên tố thứ \(n\). Bảng liệt kê 25 số nguyên tố đầu tiên.
| n | pn | n | pn | n | pn | n | pn | n | pn |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
Các mốc chỉ số
| Phát biểu | Giá trị | Ý nghĩa |
|---|---|---|
| \(p_{100}\) | 541 | Số nguyên tố thứ 100 là 541 |
| \(p_{168}\) | 997 | Số nguyên tố thứ 168 là 997, số nguyên tố lớn nhất nhỏ hơn 1000 |
| \(p_{1000}\) | 7919 | Số nguyên tố thứ 1000 là 7919 |
| \(\pi(10)\) | 4 | Các số nguyên tố không vượt quá 10: 2, 3, 5, 7 |
| \(\pi(100)\) | 25 | 25 số nguyên tố không vượt quá 100 (số cuối là 97) |
| \(\pi(1000)\) | 168 | 168 số nguyên tố không vượt quá 1000 |
| \(\pi(10000)\) | 1229 | 1229 số nguyên tố không vượt quá 10.000 |
Lưu ý mối liên hệ giữa hai ký hiệu: nếu \(p\) là số nguyên tố, thì \(\pi(p) = n\) khi và chỉ khi \(p = p_n\). Ví dụ, \(\pi(997) = 168\) và \(p_{168} = 997\).
Giải thích các thuật ngữ về số nguyên tố
- Số nguyên tố: số nguyên lớn hơn 1 mà các ước dương duy nhất của nó là 1 và chính nó (ví dụ 2, 3, 5, 7, 11).
- Hợp số: số nguyên lớn hơn 1 có ít nhất một ước khác 1 và chính nó (ví dụ 4, 6, 9, 15).
- Số 1 là trường hợp đặc biệt: số 1 không phải số nguyên tố cũng không phải hợp số. Nó chỉ có một ước dương duy nhất, là chính nó.
- 2 là số nguyên tố chẵn duy nhất: mọi số chẵn khác đều chia hết cho 2 nên là hợp số.
- Chỉ số (vị trí) n của số nguyên tố: thứ hạng của một số nguyên tố trong danh sách các số nguyên tố được sắp xếp. 2 có chỉ số 1, 3 có chỉ số 2, 5 có chỉ số 3, và cứ tiếp tục như vậy, nên \(p_n\) biểu thị số nguyên tố thứ \(n\).
- Hàm đếm số nguyên tố \(\pi(x)\): số lượng các số nguyên tố nhỏ hơn hoặc bằng \(x\). Ví dụ \(\pi(10) = 4\) và \(\pi(100) = 25\).
- Phép thử chia thử: phép kiểm tra tính nguyên tố bằng cách thử chia \(p\) cho từng số nguyên \(d\) từ 2 đến \(\sqrt{p}\). Nếu không có số nào chia hết \(p\), thì \(p\) là số nguyên tố. Chỉ cần kiểm tra đến \(\sqrt{p}\) là đủ, vì trong mỗi cặp thừa số có một số không vượt quá \(\sqrt{p}\).
- Nguyên tố cùng nhau: hai số nguyên là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Hai số nguyên tố khác nhau luôn nguyên tố cùng nhau, nhưng các số nguyên tố cùng nhau không nhất thiết là số nguyên tố (8 và 15 nguyên tố cùng nhau).
- Số nguyên tố sinh đôi: một cặp số nguyên tố hơn kém nhau 2, chẳng hạn (3, 5), (11, 13), (17, 19), (29, 31) và (41, 43).
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\).