Kiểm tra tính nguyên tố [tiếng Anh: primality test] là bài toán kiểm tra xem một số tự nhiên n {\displaystyle n} có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m {\displaystyle m} nằm trong khoảng 2 đến n − 1 {\displaystyle n-1} hay không. Nếu n {\displaystyle n} chia hết cho một số m {\displaystyle m} nào đó thì n {\displaystyle n} là hợp số [composite], ngược lại n {\displaystyle n} là số nguyên tố.
Thực ra việc kiểm tra với m {\displaystyle m} từ 2 đến n − 1 {\displaystyle n-1} là không cần thiết, mà chỉ cần kiểm tra đến n {\displaystyle {\sqrt {n}}} . Đó là vì nếu n {\displaystyle n} là hợp số thì nó chắc chắn có ước số không vượt quá n {\displaystyle {\sqrt {n}}} .
Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp m = 2 {\displaystyle m=2} bằng cách chỉ xét các số lẻ. Đi xa hơn một chút, ta chỉ cần xét các số dạng 6 k ± 1 {\displaystyle 6k\pm 1} và bỏ qua việc kiểm tra 2 trường hợp m = 2 {\displaystyle m=2} và m = 3 {\displaystyle m=3} . Đó là vì tất cả các số nguyên tố đều có dạng 6 k + i {\displaystyle 6k+i} với k {\displaystyle k} nào đó và i = 0 , ± 1 , ± 2 {\displaystyle i=0,\pm 1,\pm 2} ; mà trong đó 6 k + 0 {\displaystyle 6k+0} , 6 k + 2 {\displaystyle 6k+2} , 6 k + 4 {\displaystyle 6k+4} chia hết cho 2, còn 6 k + 3 {\displaystyle 6k+3} thì chia hết cho 3. Tiếp tục với các nhận xét đó, ta có thể tổng quát hóa thành thuật toán sàng Eratosthenes.
Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q[p,a] nào đó đúng với mọi số nguyên tố p và một số tự nhiên a