Hiểu kết quả
Bảng dưới đây trình bày ba kết quả đầu ra cho một số ví dụ đầu vào.
| Đầu vào | Nguyên tố? | Phân tích thừa số | Số nguyên tố kế tiếp |
|---|---|---|---|
| 97 | Có | 97 | 101 |
| 84 | Không | 2 x 2 x 3 x 7 | 89 |
| 100 | Không | 2 x 2 x 5 x 5 | 101 |
| 2 | Có (số nguyên tố chẵn duy nhất) | 2 | 3 |
| 1 | Không (không nguyên tố cũng không phải hợp số) | - | 2 |
- Số 1 không phải số nguyên tố: số nguyên tố phải có đúng hai ước phân biệt, còn 1 chỉ có một ước. Việc loại trừ số 1 giữ được tính duy nhất của phân tích thừa số nguyên tố.
- Phép chia thử cho kết quả chính xác nhưng chậm với đầu vào rất lớn; máy tính này nhận các số đến 10^12, khi đó quá trình tìm kiếm thử các ước đến một triệu.
- Việc tìm số nguyên tố kế tiếp chắc chắn kết thúc nhanh trong khoảng này: theo định đề Bertrand, luôn tồn tại một số nguyên tố nằm giữa n và 2n.
Số nguyên tố là gì?
Số nguyên tố là số tự nhiên lớn hơn 1 có đúng hai ước dương: 1 và chính nó. Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23 và 29. Số 2 là số nguyên tố chẵn duy nhất, vì mọi số chẵn khác đều chia hết cho 2. Những số lớn hơn 1 mà không phải số nguyên tố được gọi là hợp số; theo định nghĩa, số 1 không phải số nguyên tố cũng không phải hợp số.
Định lý cơ bản của số học phát biểu rằng mọi số nguyên lớn hơn 1 đều viết được thành tích các số nguyên tố theo đúng một cách duy nhất, không kể thứ tự các thừa số. Chính tính duy nhất của phân tích thừa số nguyên tố khiến các số nguyên tố được gọi là viên gạch xây nên tập số nguyên: 84 = 2^2 x 3 x 7, và không có tổ hợp số nguyên tố nào khác nhân lại cho 84.
Số nguyên tố có vô hạn — kết quả do Euclid chứng minh vào khoảng năm 300 trước Công nguyên — và chúng thưa dần khi số lớn lên, tuy không theo quy luật đơn giản nào. Các số nguyên tố lớn là nền tảng của mật mã khóa công khai hiện đại (chẳng hạn RSA), vốn dựa vào độ khó thực tế của việc phân tích tích hai số nguyên tố rất lớn.
Cách dùng máy tính số nguyên tố này
- Nhập một số nguyên n ít nhất bằng 1. Số thập phân sẽ được làm tròn xuống số nguyên gần nhất.
- Đọc kết luận về tính nguyên tố: dấu tích nghĩa là số đó là số nguyên tố, dấu chéo nghĩa là nó là hợp số (hoặc là 1, vốn không thuộc loại nào).
- Đọc phân tích thừa số nguyên tố — tích duy nhất các số nguyên tố bằng đúng số của bạn. Với đầu vào là số nguyên tố, phân tích chính là bản thân số đó.
- Đọc số nguyên tố kế tiếp, tức số nguyên tố nhỏ nhất lớn hơn hẳn số của bạn.
Cách kiểm tra tính nguyên tố: phép chia thử
Một số n là hợp số khi và chỉ khi nó có một ước lớn hơn 1 và không vượt quá căn bậc hai của n. Lý do là các ước luôn đi thành cặp: nếu n = a x b với a <= b thì a <= sqrt(n). Vì vậy phép chia thử chỉ cần kiểm tra các ước ứng viên đến sqrt(n) — sau khi kiểm tra 2, chỉ cần xét các ứng viên lẻ.
Ví dụ minh họa (số nguyên tố): n = 97. Căn bậc hai của 97 xấp xỉ 9,85, nên chỉ cần thử 2, 3, 5, 7 và 9. Số 97 là số lẻ; 9 + 7 = 16 không chia hết cho 3; nó không tận cùng bằng 0 hay 5; 97 / 7 = 13.857...; và 97 / 9 không chia hết. Không tồn tại ước nào, vậy 97 là số nguyên tố.
Ví dụ minh họa (phân tích thừa số): n = 84. Chia dần các số nguyên tố từ nhỏ nhất: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, và 7 là số nguyên tố. Vậy 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Số nguyên tố kế tiếp sau 84 là 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Những lỗi thường gặp
- Coi 1 là số nguyên tố — theo định nghĩa, số nguyên tố có đúng hai ước phân biệt, còn 1 chỉ có một ước.
- Cho rằng mọi số nguyên tố đều lẻ: 2 là số nguyên tố, và đó là số nguyên tố chẵn duy nhất.
- Thử các ước lên đến tận n thay vì dừng ở sqrt(n) — mọi hợp số đều có một thừa số nhỏ hơn hoặc bằng căn bậc hai của nó.
- Tin rằng mọi số lẻ đều là số nguyên tố: 9 = 3 x 3, 15 = 3 x 5 và 21 = 3 x 7 đều là hợp số lẻ.
- Nhầm phân tích thừa số nguyên tố với một cách phân tích bất kỳ: 84 = 4 x 21 là một cách phân tích, nhưng phân tích thừa số nguyên tố là 2 x 2 x 3 x 7.
Câu hỏi thường gặp
Làm sao kiểm tra một số có phải số nguyên tố không?
Hãy thử xem có số nguyên nào từ 2 đến căn bậc hai của số đó chia hết nó hay không. Nếu không có số nào chia hết, đó là số nguyên tố. Với 97, căn bậc hai xấp xỉ 9,85, và không số nào trong 2, 3, 5, 7 hay 9 chia hết 97, nên 97 là số nguyên tố. Các cặp ước bảo đảm rằng mọi hợp số đều có một thừa số nhỏ hơn hoặc bằng căn bậc hai của nó.
Vì sao 1 không phải là số nguyên tố?
Số nguyên tố được định nghĩa là có đúng hai ước dương phân biệt, gồm 1 và chính nó; số 1 chỉ có một ước. Định nghĩa này còn bảo vệ định lý cơ bản của số học: nếu 1 là số nguyên tố thì phân tích thừa số sẽ không còn duy nhất (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, và cứ thế).
Phân tích thừa số nguyên tố là gì?
Đó là cách biểu diễn một số thành tích các số nguyên tố, và định lý cơ bản của số học bảo đảm cách biểu diễn này là duy nhất, không kể thứ tự. Ví dụ, 84 = 2 x 2 x 3 x 7. Để tìm nó, hãy liên tục chia cho số nguyên tố nhỏ nhất chia hết được, cho đến khi thương còn lại bằng 1 hoặc là số nguyên tố.
Số 2 có phải số nguyên tố không?
Có — 2 là số nguyên tố vì các ước duy nhất của nó là 1 và 2, và đây 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ố. Đó là lý do các thuật toán kiểm tra tính nguyên tố xử lý riêng số 2 rồi chỉ xét các ứng viên lẻ.
Có bao nhiêu số nguyên tố?
Vô hạn, như Euclid đã chứng minh vào khoảng năm 300 trước Công nguyên: cho một danh sách hữu hạn bất kỳ các số nguyên tố, số tạo thành bằng cách nhân tất cả chúng rồi cộng 1 không chia hết cho số nào trong danh sách, nên phải có số nguyên tố nào đó bị thiếu. Số nguyên tố thưa dần khi số lớn lên — theo định lý số nguyên tố, mật độ số nguyên tố quanh n xấp xỉ 1 / ln(n) — nhưng chúng không bao giờ dừng lại.
Vì sao số nguyên tố quan trọng trong mật mã học?
Các hệ khóa công khai như RSA dựa trên một sự bất đối xứng: nhân hai số nguyên tố lớn thì dễ, nhưng khôi phục lại các số nguyên tố từ tích của chúng lại rất tốn kém về mặt tính toán ở những kích thước dùng trong thực tế (hàng trăm chữ số). Khóa bảo mật được xây dựng từ các tích như vậy, nên việc sinh số nguyên tố và kiểm tra tính nguyên tố là những thao tác mật mã cốt lõi.
Tài liệu tham khảo
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).