HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>12. số trong c++

Kiểm tra số nguyên tố trong C++

3 tháng 10 ,2021

Hướng dẫn cách kiểm tra số nguyên tố trong C++. Bạn sẽ học được cách tạo hàm kiểm tra số nguyên tố trong C++ cũng như cách liệt kê tất cả các số nguyên tố nhỏ hơn n bằng C++ sau bài học này.

Số nguyên tố trong C++ là gì

Chúng ta đều biết số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó.

Ví dụ, chúng ta xem xét các số 2, 3, 6 như sau:

Số 2 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 3 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 6 có 4 ước số là 1, 2 , 3 và 6, do đó nó không phải là số nguyên tố.

Kiểm tra số nguyên tố trong C++

Số nguyên tố là số lớn hơn 1 và chỉ có đúng hai ước số là 1 và chính nó. Bởi vậy nếu số đã cho có nhiều hơn dù chỉ 1 ước số khác số 1 và chính nó thì nó không phải là số nguyên tố.

Để kiểm tra được điều này, chúng ta chỉ cần kiểm tra trong phạm vi lớn hơn 1 và nhỏ hơn số đã cho có tồn tại ước số nào không, và nếu tồn tại dù chỉ một ước số thì có thể khẳng định số đã cho không phải là số nguyên tố.

Dựa vào điều này mà chúng ta có thể tạo hàm kiểm tra số nguyên tố trong C++ dùng vòng lặp như sau:

bool laSoNguyenTo(int n) {
    if (n <= 1) return false; //Số nhỏ hơn 2 không phải số nguyên tố

     //Sử dụng vòng lặp để kiểm tra có tồn tại ước số nào khác
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) { //Chỉ cần tìm thấy 1 ước số là chứng tỏ không phải số nguyên tố
            return false;
        }
    }

    return true;
}

Chúng ta có thể gọi hàm này và sử dụng để viết chương trình C++ kiểm tra số nguyên tố như dưới đây. Chương trình này có tác dụng nhập n kiểm tra n có phải số nguyên tố không không C++.

#include <iostream>

bool laSoNguyenTo(int n) {
    if (n <= 1) return false;

    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int soNhap;
    std::cout << "Nhap mot so nguyen: ";
    std::cin >> soNhap;

    if (laSoNguyenTo(soNhap)) {
        std::cout << soNhap << " la so nguyen to." << std::endl;
    } else {
        std::cout << soNhap << " khong phai la so nguyen to." << std::endl;
    }

    return 0;
}

Màn hình nhập liệu và kết quả chương trình C++ kiểm tra số nguyên tố sẽ như sau:

Nhap so tu nhien= 1
1 khong phai la so nguyen to

Nhap so tu nhien= 2
2 la so nguyen to

Nhap so tu nhien= 3
3 la so nguyen to

Nhap so tu nhien= 4
4 khong phai la so nguyen to

Nhap so tu nhien= 5
5 la so nguyen to

Nhap so tu nhien= 6
6 khong phai la so nguyen to

Liệt kê tất cả các số nguyên tố nhỏ hơn n

Sử dụng phương pháp ở trên, chúng ta có thể liệt kê tất cả các số nguyên tố nhỏ hơn n bằng C++.

Và dưới đây là ví dụ về chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n trong C++:

#include <iostream>
using namespace std;

bool laSoNguyenTo(int n) {
    if (n <= 1) return false;

    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main(){
    int n;
 
    cout << (">> nhap mot so n: ");
    cin >>  n;
    int i = 0, check;
    while ( i < n){    
        if( laSoNguyenTo(i)) cout << i <<" ";
        
        ++i;
    }
    return 0;
}

Kết quả:

>> nhap mot so n: 20
2 3 5 7 11 13 17 19 

>> nhap mot so n: 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Ứng Dụng Của Số Nguyên Tố Trong Lập Trình:

Số nguyên tố có nhiều ứng dụng quan trọng trong lập trình.

Mã Hóa và Bảo Mật:

Trong mã hóa và bảo mật, số nguyên tố thường được sử dụng để tạo các khóa an toàn.

Tối Ưu Hóa:

Số nguyên tố cũng được sử dụng trong nhiều thuật toán tối ưu hóa, như thuật toán sàng Eratosthenes để tìm tất cả các số nguyên tố trong một khoảng.

Kiểm Tra Điều Kiện:

Trong một số ứng dụng, đặc biệt là trong game và đồ họa máy tính, số nguyên tố có thể được sử dụng để kiểm tra điều kiện và tạo hiệu ứng đặc biệt.

Thách Thức và Hạn Chế:

Mặc dù số nguyên tố là một khái niệm quan trọng, nhưng cũng có những thách thức và hạn chế cần được lưu ý.

Hiệu Suất:

Kiểm tra số nguyên tố có thể trở nên tốn kém đối với các số lớn. Có các thuật toán tối ưu hóa để giảm thiểu thời gian kiểm tra.

Số Nguyên Tố Lớn:

Khi làm việc với số nguyên tố lớn, chúng ta có thể đối mặt với vấn đề hiệu suất và bộ nhớ.

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn cách kiểm tra số nguyên tố trong C++ rồi. Số nguyên tố trong C++ không chỉ là một đề tài toán học thú vị mà còn là một yếu tố quan trọng trong lập trình. Việc hiểu cách kiểm tra và sử dụng số nguyên tố có thể mở ra nhiều cánh cửa sáng tạo trong việc giải quyết vấn đề và tối ưu hóa mã nguồn. Tuy nhiên, cũng cần lưu ý đến những thách thức như hiệu suất khi làm việc với các số lớn. Điều này đặt ra thách thức và yêu cầu lập trình viên phải cân nhắc kỹ lưỡng khi sử dụng số nguyên tố trong ứng dụng của mình.