Máy tính kiểm tra số nguyên tố

Định nghĩa số nguyên tố: số tự nhiên > 1 chỉ chia hết cho 1 và chính nó. Vd: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31…

Phép kiểm tra cơ bản: kiểm tra n có chia hết cho bất kỳ số nào từ 2 đến √n. Nếu không → n là số nguyên tố.

Phân tích thừa số nguyên tố: mỗi số tự nhiên > 1 có thể viết DUY NHẤT thành tích các số nguyên tố (định lý cơ bản số học).

Ví dụ:

• 360 = 2³ × 3² × 5
• 1024 = 2¹⁰
• 2024 = 2³ × 11 × 23

Tính chất quan trọng:

• 2 là số nguyên tố CHẴN DUY NHẤT
• Có vô hạn số nguyên tố (Euclid chứng minh)
• Khoảng cách trung bình giữa các số nguyên tố ≈ ln(n) — càng lớn càng thưa
• Số nguyên tố Mersenne: 2^p − 1 (vd 31, 127, 8191) — dạng đặc biệt dùng tìm số nguyên tố lớn

Số nguyên tố lớn nhất tìm được (2024):

M_82589933 = 2^82,589,933 − 1, có 24,862,048 chữ số (GIMPS 2018).

1. Nhập số nguyên dương n (1 ≤ n ≤ 10¹²).
2. Nhấn “Kiểm tra”. Kết quả:
   • n là số nguyên tố / hợp số / số 1
   • Phân tích thừa số nguyên tố (nếu là hợp số)
   • Danh sách tất cả ước
   • Số nguyên tố gần nhất (trước và sau)

Sàng Eratosthenes — cách tìm nhiều số nguyên tố cùng lúc hiệu quả hơn thử từng số

Khối đầu bài đề cập thuật toán kiểm tra cơ bản: chia n cho mọi số từ 2 đến √n. Cách này tốt cho kiểm tra một số cụ thể, nhưng khi cần tìm tất cả số nguyên tố đến N, sàng Eratosthenes hiệu quả hơn nhiều — phát minh từ thế kỷ 3 trước Công nguyên và vẫn là nền tảng của nhiều thuật toán hiện đại:

1. Viết tất cả số từ 2 đến N.
2. Bắt đầu từ số nhỏ nhất chưa bị gạch (số 2) — đây là số nguyên tố. Gạch tất cả bội số của 2 (4, 6, 8…).
3. Tiếp tục với số chưa bị gạch tiếp theo (số 3) — gạch tất cả bội số của 3 (9, 15, 21…; 6, 12… đã bị gạch rồi).
4. Lặp lại cho đến khi đã xét hết số đến √N — tất cả số còn lại chưa bị gạch đều là số nguyên tố.

Ví dụ: tìm số nguyên tố đến 30. Gạch bội của 2, 3, 5 (vì √30 ≈ 5.5 → chỉ cần xét đến 5). Kết quả còn lại: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — đúng 10 số nguyên tố.

Lý do chỉ cần kiểm tra đến √n: nếu n có ước số a > √n thì phải có ước số b = n/a < √n. Tức là ước số nhỏ hơn đã được phát hiện trước rồi. Điều này cũng là cơ sở của thuật toán kiểm tra cơ bản trong khối đầu bài — và để tính √n chính xác, bạn có thể dùng tính căn bậc hai online trên VJOL khi cần kiểm tra thủ công số lớn.

Cách dùng công cụ số nguyên tố trên VJOL — hai chức năng chính

Công cụ hỗ trợ hai bài toán độc lập, chọn theo nhu cầu:

Chức năng 1 — Kiểm tra số nguyên tố:

1. Nhập số tự nhiên n cần kiểm tra (từ 2 trở lên).
2. Bấm “Kiểm tra”. Công cụ chạy thuật toán thử chia đến √n.
3. Kết quả: “n là số nguyên tố” hoặc “n không phải số nguyên tố — chia hết cho [ước số nhỏ nhất tìm được]”.

Chức năng 2 — Phân tích thừa số nguyên tố:

1. Nhập số tự nhiên n > 1 cần phân tích.
2. Bấm “Phân tích”. Công cụ lần lượt chia n cho các số nguyên tố nhỏ nhất cho đến khi thương bằng 1.
3. Kết quả: biểu diễn dạng tích lũy thừa các số nguyên tố (ví dụ: 360 = 2³ × 3² × 5) kèm bảng các bước chia.

Lưu ý: với số rất lớn (trên 10 chữ số), thuật toán thử chia đơn giản trở nên chậm vì phải kiểm tra đến √n. Các thuật toán chuyên dụng như Miller-Rabin (kiểm tra xác suất) hoặc sàng Pollard Rho (phân tích nhanh) dùng cho số hàng triệu chữ số — ngoài phạm vi công cụ cơ bản này.

Ứng dụng thực tế — số nguyên tố bảo vệ mọi giao dịch internet của bạn

Số nguyên tố không chỉ là bài tập toán học — chúng là nền tảng của bảo mật kỹ thuật số hiện đại:

• Mã hóa RSA — bảo mật HTTPS và chữ ký số: Khi bạn mở một trang web có ổ khóa xanh (HTTPS), trình duyệt và server đang sử dụng RSA — thuật toán dựa trực tiếp vào việc phân tích thừa số nguyên tố cực kỳ khó. Hai số nguyên tố lớn p và q được chọn ngẫu nhiên (mỗi số khoảng 617 chữ số thập phân với khóa 2048 bit), nhân lại thành n = p × q. Khóa công khai dùng n, nhưng giải mã đòi hỏi biết p và q riêng biệt. Phân tích ngược n để tìm lại p, q là bài toán mà ngay cả siêu máy tính hiện đại cũng không thể giải trong thời gian hợp lý — đây là tường thành bảo vệ mọi giao dịch ngân hàng, email và mua sắm trực tuyến của bạn.
• Hàm băm và bảng phân tán (hash table): Nhiều thuật toán chọn số nguyên làm kích thước bảng hoặc hệ số nhân trong hàm băm vì số nguyên tố có tính phân phối đều tốt hơn số hợp. Python dùng số nguyên như 5381 và 37 làm hằng số trong thuật toán hash nội bộ.
• Kiểm tra và sửa lỗi (error correction): Reed-Solomon codes — dùng trong QR code, Blu-ray, đĩa CD và truyền dữ liệu vệ tinh — xây dựng trên số học đa thức modulo số nguyên tố. Khi QR code bị che một phần vẫn đọc được, đó là nhờ tính chất số nguyên tố.
• Sinh số giả ngẫu nhiên (PRNG): Nhiều bộ sinh số ngẫu nhiên dùng số nguyên tố lớn trong công thức để đảm bảo chu kỳ dài và phân phối đều — quan trọng trong mô phỏng khoa học và trò chơi máy tính.

Phân tích thừa số một số con số thú vị

Ngoài ba ví dụ trong khối đầu bài (360, 1024, 2024), đây là một số con số hay gặp và kết quả phân tích của chúng:

Sai lầm thường gặp khi làm việc với số nguyên tố

Bốn lỗi phổ biến nhất trong bài tập và ứng dụng thực tế:

• Coi số 1 là số nguyên tố: Số 1 KHÔNG phải số nguyên tố theo định nghĩa hiện đại — vì nếu 1 là nguyên tố, định lý phân tích duy nhất sẽ bị phá vỡ (12 = 2²×3 = 1×2²×3 = 1²×2²×3 = … — không còn duy nhất). Định nghĩa số nguyên tố yêu cầu “có đúng 2 ước số dương phân biệt”, và 1 chỉ có 1 ước số là chính nó.
• Nhầm “số lẻ” với “số nguyên tố”: Không phải số lẻ nào cũng là nguyên tố: 9 = 3×3, 15 = 3×5, 25 = 5×5, 35 = 5×7… đều là số lẻ nhưng không phải nguyên tố. Và số 2 — số chẵn duy nhất — lại là số nguyên tố.
• Kiểm tra thiếu khi xác định số nguyên tố thủ công: Để kiểm tra 97 có phải nguyên tố không, chỉ cần thử chia cho 2, 3, 5, 7 (vì √97 ≈ 9.85 → chỉ cần xét đến 9). Nhiều người kiểm tra quá ít hoặc quá nhiều, dẫn đến sai. Nhớ: chỉ cần thử đến √n và chỉ cần thử các số nguyên tố (không cần thử số hợp như 4, 6, 8…).
• Tưởng phân tích thừa số nguyên tố có nhiều cách: Định lý cơ bản số học đảm bảo phân tích thừa số nguyên tố của mỗi số là DUY NHẤT (không kể thứ tự). 360 = 2³×3²×5 — không có cách phân tích thành tích nguyên tố nào khác. Có thể đi theo đường khác (chia cho 4 trước hay 5 trước) nhưng kết quả cuối cùng luôn như nhau.

Câu hỏi thường gặp

Làm sao nhận biết nhanh số có chia hết cho 3 không, mà không cần chia tay?

Tổng các chữ số chia hết cho 3 → số đó chia hết cho 3. Ví dụ: 2024 → 2+0+2+4 = 8 → không chia hết cho 3. Tương tự: chia hết cho 9 khi tổng chữ số chia hết cho 9. Đây là cách lọc nhanh khi phân tích thừa số thủ công.

Có công thức nào tạo ra tất cả số nguyên tố không?

Không — đây là một trong những câu hỏi cổ điển chưa có lời giải hoàn hảo. Các công thức như n² + n + 41 (của Euler) cho số nguyên tố với nhiều giá trị n nhưng không phải tất cả (n=40 cho 1681 = 41², không phải nguyên tố). Sự phân bố của số nguyên tố được mô tả thống kê bởi định lý số nguyên tố: số lượng số nguyên tố đến N xấp xỉ N/ln(N).

Giả thuyết Goldbach là gì và đã chứng minh được chưa?

Giả thuyết Goldbach (1742): mọi số chẵn lớn hơn 2 đều có thể viết thành tổng của hai số nguyên tố. Ví dụ: 28 = 5 + 23, 100 = 3 + 97 = 11 + 89. Đây là một trong những bài toán chưa giải được nổi tiếng nhất trong toán học — đã kiểm tra máy tính cho mọi số chẵn đến 4 × 10¹⁸ nhưng chứng minh tổng quát vẫn chưa có.

Tại sao cần số nguyên tố rất lớn cho mã hóa RSA?

Độ an toàn RSA dựa vào việc cho n = p × q (tích hai nguyên tố) là dễ tính, nhưng từ n tìm ngược ra p và q là cực kỳ khó. Với p, q mỗi số khoảng 1024 bit (~309 chữ số thập phân), n có khoảng 617 chữ số — phân tích n bằng máy tính nhanh nhất hiện nay có thể mất hàng nghìn năm. Khuyến cáo hiện tại là dùng khóa RSA tối thiểu 2048 bit.

Máy tính số nguyên tố trên VJOL kiểm tra ngay một số có phải nguyên tố không và phân tích thừa số nguyên tố — hai thao tác nền tảng trong lý thuyết số và mật mã học. Từ bài tập lớp 6 đến thuật toán bảo mật HTTPS, số nguyên tố xuất hiện ở khắp nơi trong khoa học máy tính hiện đại.

Xem thêm các công cụ liên quan

• công cụ chuyển đổi đơn vị online — chuyển đổi nhanh giữa các đơn vị đo lường: khối lượng, chiều dài, nhiệt độ, thể tích và nhiều loại khác.
• máy tính chỉ số BMI — tính chỉ số khối cơ thể từ cân nặng và chiều cao, kèm phân loại theo chuẩn WHO châu Á.
• tính chuyển hoá cơ bản BMR — tính lượng calo tối thiểu cơ thể cần mỗi ngày để duy trì chức năng sống cơ bản.
• VJOL Info — kho tạp chí khoa học Việt Nam trực tuyến, truy cập miễn phí do Bộ Khoa học và Công nghệ quản lý.