Trang chủLập trìnhLập trình C/C++Đếm số lượng số nguyên tố nhỏ hơn n lập trình C/C++

Đếm số lượng 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ẽ cùng đi giải quyết bài toán đếm số lượng số nguyên tố nhỏ hơn n trong lập trình C/C++.

Đếm số lượng số nguyên tố nhỏ hơn n

Ý tưởng bài toán này cũng tương đối đơn giản, đầu tiên chúng ta sẽ viết một hàm để kiểm tra một số có phải là số nguyên tố không. Sau đó chúng ta khai báo 1 biến đếm với giá trị ban đầu bằng 0, ta duyệt vòng lặp từ 1 tới n và gọi hàm kiểm tra xem số thứ i có phải là số nguyên tố không, nếu là số nguyên tố tăng biến đếm lên 1, sau khi hết vòng lặp ta in ra biến đếm chính là số lượng số nguyên tố.

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

#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
    
    int dem = 0; //Khởi tạo biến dem = 0
    for(int i=1;i<n;i++){
    	if(checkNT(i) == true)
    	 dem++; //Nếu i là số nguyên tố thì tăng biến đếm len 1
	}
     
     printf("So luong so nguyen to nho hon %d: %d",n, dem);//In so luong so nguyen to
}

Trong trường hợp đề bài yêu cầu là đếm 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é.

Cảm ơn bạn đã đọc bài viết! CHÚC HỌC TỐT NHÉ!

XÊM THÊM
Cách tìm UCLN và BCNN
Thuật toán đếm số lượng chữ số của số nguyên dương n
Thuật toán tính dãy số Fibonacci
Bài toán chuẩn hóa xâu ký tự

[Xem tất cả bài viết chủ đề C/C++ tại đây]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x