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

Tìm hiểu về số nguyên tố là gì?

Theo định nghĩa của Wikipedia thì Số nguyên tố là số tự nhiên lớn hơn 1 không thể được hình thành bằng cách nhân 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ố.

Ví dụ: 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ó số hạng là chính số 5. Tuy nhiên, 6 là hợp số vì nó là tích của hai số (2 × 3) đều nhỏ hơn 6. Các số nguyên tố là trung tâm trong lý thuyết số vì định lý cơ bản của số học: mọi số tự nhiên lớn hơn 1 đều là số nguyên tố hoặc có thể được phân tích nhân tử thành tích của các số nguyên tố mà là duy nhất theo thứ tự của chúng.

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 - 6 không tồn tại số nào mà 7 chia hết cả.

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

Dựa vào các ngôn ngữ lập trình java, c, c++, php thì chúng ta có thể thực hiện các thuật toán như dưới đây.
Thuật toán 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ố.
Sau đây là hàm kiểm tra số nguyên tố sử dụng ngôn ngữ lập trình c

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;
}

Thuật toán 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.

Sau đây là chương trình kiểm tra số nguyên tố:

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;
}