Số Nguyên Tố Trong C++ cách kiểm tra hay nhất 2023✅

Bạn đã biết cách kiểm tra số nguyên tố trong C++ chưa? Đọc ngay bài viết dưới đây của Tekmonk để họ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ố Là Gì?

Bạn đã biết số nguyên tố là gì. Vậy bạn có thắc mắc các tính chất đặc trưng của số nguyên tố là gì không? Dưới đây là các thông tin chi tiết về các tính chất này. Nắm rõ điều này sẽ giúp bạn tính toán số nguyên tố nhanh chóng, dễ dàng hơn.

• 2 là số nguyên tố chẵn duy nhất. Đây cũng là số nguyên tố nhỏ nhất.
• Ước tự nhiên nhỏ nhất #1 của một số tự nhiên là số nguyên tố.
• Số nguyên tố là vô hạn.
• Tích của 2 số nguyên tố không thể là một số chính phương.
• Một tập hợp số c bất kỳ có ước nhỏ nhất là một số dương (x) với điều kiện x #1 và x< √c thì x là số nguyên tố.

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

Hướng dẫn các cách tìm số nguyên tố

Dưới đây là một số cách tìm số nguyên tố mà bạn có thể tham khảo để áp dụng khi cần.

• Cách 1: Tìm số nguyên tố A trong khoảng 2 – (A – 1)

Nếu A < 2 thì A không phải số nguyên tố

Nếu A > 2 và trong khoảng 2 – (A- 1) không có số A chia hết thì A là số nguyên tố.

Ví dụ A = 13, trong khoảng 2 – 12 có các số 3, 4, 5, 6, 7, 8, 9, 10, 11, 12; 13 không chia hết cho số nào => 13 là một số nguyên tố.

• Cách 2: Tìm số nguyên tố A trong khoảng 2 – (A – 2)

Nếu trong khoảng 2 – (A – 2) có số lẻ mà A không chia hết thì A là số nguyên tố.

Ví dụ A = 13, trong khoảng 2 – 11 có các số lẻ là 3, 5, 7, 9; 13 không chia hết cho số nào => 13 là một số nguyên tố.

• Cách 3: Dùng máy tính cầm tay tìm số nguyên tố

Để kiểm tra xem A có phải số nguyên tố không, bạn thực hiện như sau: Nhập A > “=” > Shift + FACT.

Nếu kết quả hiển thị là A thì A là số nguyên tố.

Nếu kết quả hiển thị là phép nhân thì A không phải số nguyên tố.

Các thuật ngữ liên quan đến số nguyên tố

Sau khi đã biết số nguyên tố là số gì, bạn có thể tham khảo thêm một số thuật ngữ / khái niệm liên quan đến các con số này ngay dưới đây!

• Số nguyên tố cùng nhau

Số a và số b được gọi là số nguyên tố cùng nhau nếu ước chung lớn nhất của a và b là 1.

Ví dụ như số 5 và số 23 là nguyên tố cùng nhau vì cả 2 số đều có ước chung lớn nhất là 1.

• Số siêu nguyên tố

Số abc được gọi là số siêu nguyên tố nếu bỏ c hoặc bc đi thì a vẫn là số nguyên tố. Ví dụ 1337 là số siêu nguyên tố có 4 chữ số vì nếu bỏ đi số 7 hay 37 thì 133 hay 13 cũng là số nguyên tố.

• Tích các thừa số nguyên tố

Tích các thừa số nguyên tố là phép nhân giữa các số nguyên tố.

Ví dụ:

6 = 2 * 3 trong đó 2 và 3 là các số nguyên tố

105 = 3 * 5 * 7. Trong đó 3, 5 và 7 là các số nguyên tố.

Cách Kiểm Tra Số Nguyên Tố Trong C++ Dùng While

+ Cấu trúc vòng lặp do while

Cấu trúc vòng lặp do-while là: do { <khối lệnh> } while (<điều kiện>)

Vậy nên khi bạn chuyển từ vòng lặp for sang vòng lặp do while thì chỉ cần thay thế:

Khối lệnh trong do là những gì thực hiện trong vòng lặp for:

if(n%i==0) demuoc++; i++;

Và đừng quên theo sau nó vẫn còn biến i++ nữa nhé, mỗi lần lặp nó sẽ tăng lên 1 đơn vị.

Điều kiện trong while là: điều kiện trong for: i<=n

+ CODE SỐ NGUYÊN TỐ DO WHILE TRONG C++

#include <iostream>
using namespace std;
int main()
{
    int i=1,n,demuoc=0;  
    cout<<"nhap n = ";cin>>n;  
    do
    {
        if(n%i==0)  demuoc++; i++;
     }
    while (i<=n);     
    if (demuoc==2) cout<<"la so nguyen to";  
    else cout<<"khong la so nguyen to";
}

Kết quả khi chạy chương trình:

nhap n = 11
la so nguyen to
Dãy số nguyên tố <100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Dùng Đệ Quy Kiểm Tra Số Nguyên Tố trong c++

Dưới đây là một chương trình minh họa sử dụng đệ quy trong C++. Bạn chú ý, trong thân hàm recurse() có lời gọi hàm tới chính nó => đó là hàm đệ quy.

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}
 
int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

Vậy 1 chương trình sẽ chạy như thế nào nếu có hàm đệ quy? Bạn hãy xem hình ảnh dưới đây:

Như các bạn có thể thấy, khi một hàm đệ quy được gọi (ở ví dụ trên là hàm main gọi) thì thay vì hàm đó chỉ được thực thi 1 lần thì ở đây bản thân hàm gọi lại chính nó => Nó có thể tự chạy lại chính mình số lần bất kỳ.

Như vậy các bạn vừa tìm hiểu số nguyên tố là gì và hai cách để kiểm tra số nguyên tố trong c++, chúc các bạn học lập trình c++ nhanh chóng và thành công.