Bước 1: Viết dãy các bình phương của các số nguyên tố tăng dần:

$2^2=4,3^2=9,5^2=25,7^2=49,...$

Bước 2: Chọn ra số nguyên tố $p$ bé nhất sao cho $p^2>a$.

Bước 3: Chia $a$ lần lượt cho các số nguyên tố nhỏ hơn $p$. Nếu tất cả các phép chia đều có dư thì $a$ là số nguyên tố. Ngược lại thì $a$ là hợp số.

Ví dụ: Kiểm tra 53 có phải số nguyên tố hay không?

- Dãy bình phương các số nguyên tố viết theo thứ tự tăng: $2^2=4,3^2=9,5^2=25,7^2=49,11^2=121...$

- Ta thấy $49< 53< 121$ nên các số nguyên tố có bình phương nhỏ hơn $53$ là $2,3,5,7$.

- Sử dụng dấu hiệu chia hết cho $2,3,5$ ta thấy $53$ không chia hết cho $2,3,5$. Thực hiện phép chia $53$ cho $7$ được thương là $7$ dư $4$. Do đó $53$ là số nguyên tố.