Kiểm tra số nguyên tố (kèm phân tích nhân tử)

Số nguyên tố là gì

Số nguyên tố là số tự nhiên lớn hơn 1 không có ước số dương nào ngoài 1 và chính nó. Vài số nguyên tố đầu tiên: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Chúng là 'nguyên tử' của số học nguyên — mọi số nguyên ≥ 2 đều có thể viết duy nhất dưới dạng tích của các số nguyên tố (Định lý cơ bản về số học).

1 không phải số nguyên tố theo quy ước. 0 và số âm không phải số nguyên tố. 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à số hợp.

Bài kiểm tra hoạt động như thế nào

Chúng tôi dùng phép chia thử: kiểm tra khả năng chia hết cho 2, rồi 3, rồi 5, 7, 11, … lên đến √n. Nếu không có số nào chia hết, n là số nguyên tố. Chúng tôi dùng tối ưu hóa 6k±1 chỉ kiểm tra các ứng viên dạng 6k+1 hoặc 6k−1 (vì tất cả số nguyên tố > 3 đều có dạng này), giảm số lần kiểm tra đi 2/3.

Phép chia thử nhanh với n tới ~10^15 (dưới một giây). Ngoài đó, cần các bài kiểm tra nâng cao như Miller-Rabin (xác suất) hoặc AKS (xác định). Chúng tôi giới hạn ở 10^18 để ngăn trình duyệt bị treo với đầu vào cực lớn.

Tại sao số nguyên tố quan trọng

Mật mã học: mã hóa RSA nhân hai số nguyên tố ~1000 chữ số để tạo ra một số khó phân tích nhân tử. Bảo mật dựa vào sự khó khăn của việc phân tích số lớn — thách thức đã được nghiên cứu hàng nghìn năm.

Giáo dục toán: phân tích nhân tử nguyên tố là nền tảng. Các khái niệm như GCD, LCM, số học modular, phân số và lý thuyết số đều xây dựng trên cấu trúc nhân tử nguyên tố.

Khoa học máy tính: kích thước bảng băm, bộ tạo số ngẫu nhiên và nhiều thuật toán dùng số nguyên tố vì tính chất khả năng chia hết đặc biệt của chúng.