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.
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.
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ố.
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.
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ố.
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ố.
Để 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ố.
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ố 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ố 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ố 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ấ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
#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ướ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.
