Kiểm tra số nguyên tố (prime number) trong C++

1. Như thế nào là một số nguyên tố (prime number)?

Một số nguyên dương chỉ chia hết cho 1 và chính nó được gọi là số nguyên tố. Ví dụ, 2, 3, 5, 7, 11, 13, 17, 19, 23,… là các số nguyên tố. Lưu ý: 0 và 1 không phải là số nguyên tố.

Ý tưởng kiểm tra một số nguyên dương n có phải là số nguyên tố hay không?

1. Nếu số nguyên dương n là 0 hoặc 1 thì kết luận không phải là số nguyên tố.

2. Nếu n không chia hết cho bất kỳ số nào từ 2 đến n-1 thì kết luận n là số nguyên tố. Ngược lại, kết luận n không phải là số nguyên tố.

Dễ thấy, chỉ có số 2 là số nguyên tố chẵn, tất cả các số chẵn khác không phải là số nguyên tố vì chúng chia hết cho 2. Do đó, thay vì phải duyệt từ 2 đến n-1, chúng ta có thể chỉ xem xét từ 2 đến n/2.

Ngoài ra, người ta đã chứng minh được rằng: chỉ cần kiểm tra xem n có chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của n để xác định xem n có phải số nguyên tố hay không.

2. Chương trình kiểm tra số nguyên tố trong C++

Sử dụng vòng lặp for trong C++ để kiểm tra n có chia hết cho bất kỳ số nào từ 2 đến n-1 hay không?

Lưu ý: Muốn kiểm tra người dùng nhập số nguyên dương hợp lệ hay không thì các bạn xem lại bài đếm số chữ số của một số nguyên dương trong C++.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    bool is_prime = true;
    // 0 and 1 are not prime numbers
    if (n == 0 || n == 1) {
        is_prime = false;
    }
    // loop to check if n is prime
    for (int i = 2; i <= n-1; i++) {
        if (n % i == 0) {
            is_prime = false;
            break;
        }
    }
    if (is_prime) {
        cout<<n<<" is a prime number";
    } else {
        cout<<n<<" is not a prime number";
    }
    return 0;
}

Chúng ta có thể thay đổi điều kiện lặp trong for để chỉ chạy từ 2 đến n/2.

// loop to check if n is prime
for (int i = 2; i <= num/2; i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng ta có thể thay đổi điều kiện lặp trong for để chỉ chạy từ 2 đến căn bậc 2 của n (sqrt(n)). Lưu ý: Ta cần thêm thư viện #include <math.h> để sử dụng được hàm sqrt().

// loop to check if n is prime
for (int i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng ta chỉ nên duyệt đến căn bậc 2 của n để làm ngắn gọn số lần lặp trong for.

3. Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng số N

Một bài tập C++ thường gặp là liệt kê tất cả số nguyên tố trong dãy từ 1 đến N. Chương trình bên dưới giúp giải bài tập này.

#include <iostream>
#include <math.h>
using namespace std;

bool isPrime(int n){
	bool is_prime = true;
    // 0 and 1 are not prime numbers
    if (n == 0 || n == 1) {
        is_prime = false;
    }
    // loop to check if n is prime
    for (int i = 2; i <= n-1; i++) {
        if (n % i == 0) {
            is_prime = false;
            break;
        }
    }
    return is_prime;
}

int main()
{
    int n;
    cout << "Nhap vao mot so nguyen: ";
    cin >> n;
    cout<<"Cac so nguyen to nho hon hoac bang "<<n<<" la: ";
    for(int i = 2; i <= n; i++){
    	if(isPrime(i)){
    		cout<<i<<" ";
    	}
    }
    return 0;
}

Trong chương trình trên, chúng ta xây dựng hàm isPrime(int n) giúp kiểm tra một số có phải là số nguyên tố hay không. Trong hàm main(), sử dụng vòng lặp for để duyệt các số từ 2 đến n để kiểm tra số nào là số nguyên tố. Sau đó, in chúng ra màn hình.