Kiểm tra số nguyên tố và phân tích thừa số

Số nguyên tố là số tự nhiên lớn hơn 1 và không có ước dương nào khác ngoài 1 và chính nó. Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 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ố. Điều này khiến 2 trở nên đặc biệt trong các số nguyên tố. Cách kiểm tra một số có phải số nguyên tố không: chỉ cần thử chia cho các số nguyên tố không vượt quá căn bậc hai của nó. Để kiểm tra 97: thử 2, 3, 5, 7 (√97 ≈ 9,8). Nếu không số nào chia hết, đó là số nguyên tố. Có vô số số nguyên tố: khoảng năm 300 TCN, Euclid đã chứng minh rằng có vô hạn số nguyên tố. Số nguyên tố lớn nhất được biết đến (tính đến năm 2024) có hơn 40 triệu chữ số. Vì sao số nguyên tố quan trọng: mã hóa RSA (bảo mật ngân hàng trực tuyến, email, HTTPS) dựa trên thực tế rằng nhân hai số nguyên tố lớn thì dễ, nhưng phân tích tích đó trở lại thành các thừa số nguyên tố thì gần như bất khả thi về mặt tính toán.