Số nguyên tố là
số tự nhiên lớn hơn 1 không thể được hình thành bằng cách nhân hai số tự nhiên nhỏ hơn. Số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là
hợp số. Ví dụ: 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một
tích, 1 × 5 hoặc 5 × 1, có số hạng là chính số 5. Tuy nhiên, 6 là hợp số vì nó là tích của hai số (2 × 3) đều nhỏ hơn 6. Các
số nguyên tố là trung tâm trong
lý thuyết số vì
định lý cơ bản của số học: mọi số tự nhiên lớn hơn 1 đều là số nguyên tố hoặc có thể được
phân tích nhân tử thành tích của các số nguyên tố mà là duy nhất theo thứ tự của chúng.Một phương pháp đơn giản nhưng chậm để kiểm tra một số n đã cho có phải là số nguyên tố hay không, được gọi là phép chia thử nghiệm, kiểm tra xem n có là bội số của bất kỳ số nguyên nào giữa 2 và n {\displaystyle {\sqrt {n}}} . Các thuật toán nhanh hơn bao gồm
kiểm tra Miller–Rabin, tuy nhanh nhưng có khả năng xảy ra lỗi nhỏ và
phép kiểm tra tính nguyên tố AKS, mà luôn tạo ra câu trả lời đúng trong thời gian bậc đa thức của thời gian nhưng quá chậm để áp dụng trong thực tế. Phương pháp đặc biệt nhanh có sẵn cho số lượng các dạng nguyên tố đặc biệt, chẳng hạn như
các số nguyen tố Mersenne. Tính đến tháng 12 năm 2018
[cập nhật] số nguyên tố lớn nhất được biết có 23 249 425
chữ số.Có
vô số số nguyên tố, được Euclid chứng minh vào khoảng năm 300 TCN. Không có công thức đơn giản được biết đến để tách các số nguyên tố từ hợp số. Tuy nhiên, sự phân bố các số nguyên tố trong các số tự nhiên có thể được mô hình hóa theo thống kê. Kết quả đầu tiên theo hướng đó là
định lý số nguyên tố, được chứng minh vào cuối thế kỷ 19, nói rằng
xác suất của một số được chọn ngẫu nhiên là số nguyên tố
tỷ lệ nghịch với số chữ số của nó, nghĩa là với
logarit của nó.Một số câu hỏi lịch sử liên quan đến số nguyên tố vẫn chưa được giải quyết. Chúng bao gồm
giả thuyết của Goldbach, rằng mọi số nguyên chẵn lớn hơn 2 có thể được biểu diễn dưới dạng tổng của hai số nguyên tố và phỏng đoán
nguyên tố sinh đôi, rằng có vô số cặp số nguyên tố chỉ có một số chẵn giữa chúng. Những câu hỏi như vậy đã thúc đẩy sự phát triển của các nhánh khác nhau của lý thuyết số, tập trung vào các khía cạnh phân tích hoặc
đại số của các con số. Các số nguyên tố được sử dụng trong một số quy trình trong
công nghệ thông tin, chẳng hạn như
mật mã khóa công khai, dựa trên khó khăn trong việc
phân tích các số nguyên lớn thành các nhân tử của chúng. Trong
đại số trừu tượng, các đối tượng hành xử theo cách tổng quát như số nguyên tố bao gồm các phần tử nguyên tố và ideal nguyên tố.