Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán kiểm tra số nguyên tố trong ngôn ngữ lập trình C / C++. Đây là một thuật toán quan trọng trong lập...
Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán kiểm tra số nguyên tố trong ngôn ngữ lập trình c / C++. Đây là một thuật toán quan trọng trong lập trình và giúp chúng ta xác định một số có phải là số nguyên tố hay không.
Số nguyên tố là gì?
Số nguyên tố là các số chỉ có hai ước số dương là 1 và chính nó. Ví dụ về các số nguyên tố là {2, 3, 5, 7, 11, ...}. Trong danh sách các số nguyên tố, số 2 là số chẵn duy nhất và các số nguyên tố là vô hạn.
Thuật toán kiểm tra số nguyên tố trong C / C++
Có hai cách để kiểm tra một số có phải là số nguyên tố trong ngôn ngữ lập trình c / C++. Hãy tìm hiểu từng cách một.
Cách 1: Lặp từng phần tử với bước nhảy 1
Dưới đây là thuật toán kiểm tra số n có phải là số nguyên tố hay không:
- Kiểm tra điều kiện: Nếu n < 2, return false vì đây không phải là số nguyên tố.
- Sử dụng vòng lặp for với bước nhảy 1, lặp từ 2 đến n - 1. Nếu tồn tại một số nào mà n chia hết thì return false, ngược lại return true.
Cách 2: Lặp từng phần tử với bước nhảy 2
Cách này tối ưu hơn cách 1 vì ta có thể loại bỏ số 2 ra khỏi vòng lặp. Đây là cách thực hiện thuật toán:
- Kiểm tra: Nếu n < 2, đây không phải là số nguyên tố.
- Nếu n = 2, đây là số nguyên tố.
- Nếu n chia hết cho 2 [là số chẵn], không phải là số nguyên tố.
- Sử dụng vòng lặp for với bước nhảy 2, bắt đầu từ 3 đến n - 1. Nếu tồn tại số nào mà n chia hết thì đó không phải là số nguyên tố, ngược lại là số nguyên tố. *Lưu ý: Để tối ưu hơn, ta có thể sử dụng điều kiện dừng của vòng lặp là n / 2 thay vì n - 1, vì một số sẽ không bao giờ chia hết cho số lớn hơn một nửa của nó.
Ví dụ thuật toán kiểm tra số nguyên tố trong C / C++
Dưới đây là ví dụ về cách sử dụng thuật toán kiểm tra số nguyên tố trong ngôn ngữ lập trình C / C++. Chúng ta sẽ sử dụng hai cách đã trình bày ở phần trước.
Với bài tập C này, ngoài sử dụng vòng lặp, chúng ta cần kết hợp thêm một lệnh để kiểm tra điều kiện xem số đó là số chẵn hay lẻ, nếu là số lẻ thì in còn nếu là số chẵn thì không. Chúng ta sử dụng lệnh IF và toán tử % [để lấy phần dư] trong C.
Chương trình C
Dưới đây là chương trình C để giải bài tập C trên:
include
int main[] { int i; printf["In cac so le:\n"]; for[i = 1; i