Thuật toán kiểm tra số nguyên tố

Số nguyên tố là gì?

Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.

Ví dụ về số nguyên tố

Sau đây là một vài ví dụ hữu ích về số nguyên tố mà bạn có thể ghi nhớ để tiện ứng dụng trong quá trình học tập:

2 là số nguyên tố nhỏ nhất có 1 chữ số
11 là số nguyên tố nhỏ nhất có 2 chữ số
101 là số nguyên tố nhỏ nhất có 3 chữ số
97 là số nguyên tố lớn nhất có 2 chữ số
997 là số nguyên tố lớn nhất có 3 chữ số

Số nguyên tố trong lập trình

Nếu hỏi chị google "Định nghĩa số nguyên tố", câu trả lời chúng ta nhận được sẽ là: "-Theo wikipedia-, số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Chẳng hạn, 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một tích, 1 × 5 hoặc 5 × 1, có một thừa số là chính số 5...."

Cách xác định một số nguyên tố với dân lập trình:

Theo như định nghĩa ở trên, cách đơn giản nhất để xác định number có phải là số nguyên tố không là tạo ra một vòng lặp từ 2 đến number - 1, nếu number chia hết cho một số nào đó thì number là một hợp số.

Cách 1: Lặp từng phần tử với bước nhảy 1

Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:

Bước 1: Nhập vào n

Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố

Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

bool laSoNguyenTo1(int n)
{
// Neu n < 2 thi khong phai la SNT
if (n < 2){
return false;
}

for (int i = 2; i < (n - 1); i++){
if (n % i == 0){
return false;
}
}

return true;
}

Cách 2: Lặp từng phần tử với bước nhảy 2

Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.

bool laSoNguyenTo2(int n)
{
// Neu n < 2 thi khong phai la SNT
if (n < 2){
return false;
}

// Neu n = 2 la SNT
if (n == 2){
return true;
}

// Neu n la so chan thi ko phai la SNT
if (n % 2 == 0){
return false;
}

// Lap qua cac so le
for (int i = 3; i < (n - 1); i += 2){
if (n % i == 0){
return false;
}
}

return true;
}