Tổng hợp

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

Posted on by ha ngo

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

1. 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, chỉ có 2 ước là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11, … là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất.

 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ả.

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

 Dựa vào định nghĩa của số nguyên tố chúng ta sẽ có một số cách giải như sau (các ví dụ được viết bằng ngôn ngữ C++):

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ố.

     Hàm main:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void main()
    {
        int n;
        cout << "Nhap so can kiem tra";
        cin >> n;
            
        if (laSoNguyenTo1(n)){
            cout << "La so nguyen to";
        }
        else {
            cout << "Khong phai so nguyen to";
        }
    }

    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.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    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;
    }

     Hàm main:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void main()
    {
        int n;
        cout << "Nhap so can kiem tra";
        cin >> n;
            
        if (laSoNguyenTo2(n)){
            cout << "La so nguyen to";
        }
        else {
            cout << "Khong phai so nguyen to";
        }
    }

    3. Lời kết

     Vẫn còn rất nhiều cách khác nhưng chung quy lại vẫn phải bám vào định nghĩa số nguyên tố là gì. Ví dụ trong vòng lặp điểm dừng sẽ là (n/2) thay vì (n-1) vì theo lý thuyết thì một số không bao giờ chia hết cho số một nửa của nó. Ví dụ số 9 thì số một nửa của nó là số (9 : 2 = 4), như vậy ta chỉ cần kiểm tra các số từ 2,3,4 mà thôi, còn các số 5,6,7,8 chắc chẵn 9 sẽ không chia hết.

    1
    2
    3
    4
    5
    for (int i = 3; i <= (n/2); i += 2){
            if (n % i == 0){
                    return false;
            }  

      

      

     tag: nhanh pascal