Ý tưởng: Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Ta sẽ duyệt danh sách từ 2 đến sqrt(n). Nếu n chia hết cho 1 số thứ 3 thì nó không phải là số nguyên tố. Ngược lại n là số nguyên tố.
// Ham kiem tra 1 so co phai la so NT hay khong? Dung thi tra ve 1, nguoc lai tra ve 0
int KiemTraSNT(int n) {
if (n == 2) {
return 1;
}
else {
for (int i = 2; i <= int(sqrt(n)); i++)
{
if (n%i == 0) {
return 0;
}
}
}
return 1;
}