Một số nguyên tố là một số nguyên lớn hơn 1 mà chỉ có hai ước dương là 1 và chính nó. Mọi số nguyên lớn hơn 1 đều là số nguyên tố là một tích duy nhất của các số nguyên tố. Đó là Định lý cơ bản của số học: mọi số đều có thể được xây từ những “nguyên tử” cơ bản này.
Euclid đã chứng minh vào khoảng năm 300 TCN rằng có vô số số nguyên tố. Giả sử có một số nguyên tố lớn nhất p. Hãy nhân tất cả các số nguyên tố đã biết với nhau rồi cộng thêm 1. Kết quả hoặc tự nó là số nguyên tố (mâu thuẫn), hoặc có một ước nguyên tố chưa nằm trong danh sách. Vì vậy không thể có số nguyên tố lớn nhất.
15 số nguyên tố đầu tiên đến 47. Có 15 số nguyên tố dưới 50.
| Nguyên tố | # | Nguyên tố | # | Nguyên tố | # |
|---|---|---|---|---|---|
| 2 | 1 | 19 | 8 | 37 | 12 |
| 3 | 2 | 23 | 9 | 41 | 13 |
| 5 | 3 | 29 | 10 | 43 | 14 |
| 7 | 4 | 31 | 11 | 47 | 15 |
| 11 | 5 | 37 | 12 | 53 | 16 |
| 13 | 6 | 41 | 13 | 59 | 17 |
| 17 | 7 | 43 | 14 | 61 | 18 |
MemorisePi dùng các số nguyên tố từ 2 đến 7919 (1000 số nguyên tố đầu tiên). Định lý số nguyên tố cho biết số nguyên tố thứ n xấp xỉ bằng n·ln(n). Số nguyên tố thứ 1000 là 7919, khá gần với ước lượng 1000·ln(1000) ≈ 6908. Phân bố của các số nguyên tố trông ngẫu nhiên cục bộ nhưng tuân theo các quy luật toàn cục sâu sắc.
Mọi số nguyên chẵn lớn hơn 2 đều là tổng của hai số nguyên tố. Ví dụ: 4 = 2 + 2, 6 = 3 + 3, 100 = 3 + 97. Christian Goldbach nêu ra giả thuyết này năm 1742. Nó đã được kiểm tra đến những giới hạn cực lớn nhưng vẫn chưa được chứng minh.
Một số nguyên tố là một số nguyên dương lớn hơn 1 mà chỉ có các ước là 1 và chính nó. Euclid đã chứng minh có vô số số nguyên tố vào khoảng năm 300 TCN. Các số nguyên tố là nền móng của số học hiện đại, mật mã học và lý thuyết số. Mọi số nguyên lớn hơn 1 đều phân tích duy nhất thành tích các số nguyên tố.