Ta đã biết một vài số nguyên tố đầu tiên, đó là các số sau \[2,\,3,\,5,\,11,\ldots.\]
Bây giờ nếu $N$ là một số không quá lớn, thì sẽ không khó để xác định tất cả các số nguyên tố không vượt quá $N$. Phương pháp đó gọi là sàng Eratosthenes. Cơ sở của nó là, nếu $n \le N$ và $n$ không phải là số nguyên tố thì $n$ phải là bội của một số nguyên tố không vượt quá giá trị $\sqrt N$.

Đầu tiên ta liệt kê tất cả các số nguyên giữa $2$ và $N$ \[2,\,3,\,4,\,5,\ldots.\] Chúng ta sắp xếp chúng lại như sau:

1. $4,\,6,\,6,\,8,\,10,\ldots$ là những số nguyên chẵn từ $2^2$ đổ lên,
2. $9,\,15,\,21,\,27,\ldots$ là những bội của $3^2$ đổ lên,
3. $25,\,35,\,55,\,65$ là những bội của $5^2$ đổ lên

…..

Cứ tiếp tục như thế chúng ta loại bỏ tất cả những số nguyên là bội của một số nguyên tố không vượt quá $\sqrt N$ . Những số còn lại, đều là những số nguyên tố không vượt quá $N$. Tất cả những bảng số nguyên tố được lập nên đều cùng dùng phương pháp này nhưng sửa đổi một chút về mặt phương pháp, bảng số nguyên tố chính xác nhất là do Lehmer viết ra: “Danh sách các số nguyên tố từ 1 đến 10006721” Lehmer còn viết ra một bảng gọi là bảng “Bảng phân tích nhân tử của 10 triệu số đầu tiên“.

Một ví dụ với một số nguyên tố với $39$ chữ số là \[2^{127}-1=1701,41183,46046,92317,31687,30371,58841,05727,\]
và một số nguyên tố với 79 chữ số đó là \[180\left(2^{127}\right)^2+1.\]

Cho đến năm 1981 số nguyên tố lớn nhất được biết đến đó là số $2^{44497}-1$ là một số với $13395$ chữ số.

Một số khác là số $2^{257}-1$ nếu viết trong hệ thập phân thì như sau \[231,58417, 84746,32390,84714,19700,17375,81570,65399,\]\[69331,28112,80789,15168,01582,62592,79817.\]
Số trên là một hợp số, nhưng chúng ta chưa biết đến sự phân tích ra thừa số nguyên tố của nó. Việc này có thể làm được với sự tham gia của máy móc hoặc một phương pháp đặc biệt nào đó chứ chúng ta cũng không thể hoàn thành việc này với những tính toán thông thường. Bảng số nguyên tố đến $5000$ sẽ được cho biết ở những phần sau.