Liệt kê các số nguyên tố nhỏ hơn n lập trình C/C++
DANH SÁCH BÀI VIẾT Cách kiểm tra Số nguyên tố trong lập trình C/C++ Đếm số lượng số nguyên tố nhỏ hơn n lập trình C/C++ Liệt kê các số nguyên tố nhỏ hơn n lập trình C/C++ Đếm số lượng số nguyên tố trong mảng lập trình C/C++ Liệt kê các số nguyên tố trong mảng lập trình C/C++ Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Trong bài viết này chúng ta sẽ đi giải quyết bài toán Liệt kê các số nguyên tố nhỏ hơn n lập trình C/C++.
Liệt kê các số nguyên tố nhỏ hơn n
Để liệt kê các số nguyên tố nhỏ hơn n ý tưởng sẽ như sau, đầu tiên ta nhập n từ bàn phím, sau đó sẽ viết 1 hàm kiểm tra 1 số có phải là số nguyên tố hay không. Duyệt vòng lặp chạy từ 1 cho tới n, gọi hàm kiểm tra số thứ i có phải là số nguyên tố hay không, nếu có ta in số đó ra màn hình.
- Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
- Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
- Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
Ta có hàm kiểm tra một số có phải là số nguyên tố hay không như sau.
bool checkNT(int n){
if(n<2) return false;
int sq = sqrt(n);
for(int i=2;i <=sq ;i++){
if(n % i){
return false;
}
}
return true;
}
Nếu bạn không hiểu hàm này thì đọc bài viết dưới đây nhé, mình có giải thích tương đối rõ rằng rồi.
Chương trình hoàn chỉnh
>>XEM THÊM: Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
#include <stdio.h>
#include <math.h>
//Hàm ki?m tra s? nguyên t?
bool checkNT(int n)
{
if(n<2) return false;
int sq = sqrt(n);
for(int i=2;i <=sq ;i++){
if(n % i == 0){
return false;
}
}
return true;
}
int main()
{
int n;
printf("Nhap n:");
scanf("%d", &n); //Nhập n từ bàn phím
for(int i=1;i<n;i++){
if(checkNT(i) == true)
printf("%d ", i);//Nêu i là số nguyên tố thì ta in biến i ra màn hình
}
}
Trong trường hợp đề bài yêu cầu là liệt kê số lượng số nguyên tố nhỏ hơn hoặc bằng n thì chỉ cần thay đổi điều kiện i<n thành i<=n là được nhé.
[Xem tất cả bài viết chủ đề C/C++ tại đây]