Trong bài này mình sẽ trình bày thuật toán để kiểm tra một số có phải là số nguyên tố hay không, sau khi giới thiệu xong thuật toán mình sẽ sử dụng ngôn ngữ C++ để giải mẫu cho các bạn. Trước tiên chúng ta tìm hiểu định nghĩa số nguyên tố là gì đã nhé.
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: