Cách kiểm tra Số nguyên tố trong 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)

Kiểm tra số nguyên tố là một trong các bài toán rất cơ bản trong lập trình mà hầu hết các bạn khi mới làm quen với lập trình sẽ đều làm qua bài toán này. Vậy hãy cùng blog TUICOCACH.COM một lần nữa giải quyết bài toán này trên Lập trình C/C++ và tìm ra cách tối ưu nhất nhé.

Cách kiểm tra Số nguyên tố trong lập trình C/C++

Như các bạn đã biết số nguyên tố là số mà chỉ chia hết cho 1 và chính nó, cụ thệ các số nguyên tố đầu tiền trong dãy là: 2, 3, 5, 7, 11, 13, 17, 23, 27….(Số 1 không được coi là số nguyên tố).

Người mới học lập trình nhìn qua đều sẽ có thể dễ dàng nhận biết cách làm đơn giản nhất đó là chúng ta cho duyệt vòng lặp i chạy từ 2 cho tới < n(số cần kiểm tra), nếu như n chia hết cho i có thể dừng vòng lặp và kết luận n không phải là số nguyên tố, ngược lại nếu duyệt hết vòng lặp mà n không chia hết cho giá trị i nào thì kết luận n là số nguyên tố.

Cụ thể ta sẽ có coe mẫu C như sau:

#include <stdio.h>

int main()
{
	int n;//khai báo biến n kiểu số nguyên
	printf("Nhap n:");
	scanf("%d", &n);//Nhập n từ bàn phím
	
	bool check = true; //Khai bao biến check dat mặc định biến check là số nguyên tố
	if(n<2) check = false; // Nếu n < 2 thì n kg phải là số nguyên tố (số 0, số 1 và số âm kg phải là snt)

//Nếu n lớn hơn 2 duyệt vòng lặp kiểm tra
	for(int i=2;i<n;i++){
		if(n % i){ //Nếu n chia hết cho i thì ta gắn biến check = fale và có thể dừng vòng lặp
			check = false;
			break;
		}
	}
//=>Nếu duyệt hết vòng lặp mà không gặp biến i nào n chia hết thì biến check sẽ giữ nguên ban đầu là true

//Biến check là true thì n là số nguyên tố, ngược lại n kg phai là số nguyên tố
	if(check == true) printf("%d la so nguyen to", n);
	else printf("%d khong phai so nguyen to", n);
}

Ta có thể viết hàm kiểm tra số nguyên tố thành 1 hàm riêng như sau

#include <stdio.h>
//Ham Kiểm tra số nguyên tố
bool checkNT(int n)
{
	if(n<2) return false;//Nếu n nhỏ 2 trả ngay kq về cho hàm là false
	
//Duyệt vòng lặp kt
	for(int i=2;i<n;i++){
		if(n % i == 0){
			return false; //Nếu gặp trường hợp n có thể chia hết cho i thì trả kết quả cho hàm là không phải số NT
		}
	}
//Duyệt hết vòng lặp kg gặp n chia hết cho i thì kết quả hàm n là số nguyên tố
	return true;
}

int main()
{
	int n;
	printf("Nhap n:");
	scanf("%d", &n);
	

	if(checkNT(n) == true) printf("%d la so nguyen to", n);
	else printf("%d khong phai so nguyen to", n);
}

Tuy nhiên cách này mình không khuyến khích áp dụng, mà chỉ nên áp dụng đối với các bạn mới học lập trình, nếu làm thực tế chúng ta sẽ cần phải tìm cách tối ưu hơn, ví dụ với con số 1 tỉ chẳng hạn thì chúng ta cần tới tối đa 1 tỉ bước lặp để kiểm tra xem n có phải là số nguyên tố không, rõ rằng là chương trình chạy sẽ rất mất thời gian.

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

• 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%

Tối ưu thuật toán kiểm tra số nguyên tố

Nếu một số n mà có ước là một số x thì sẽ tồn tại một số (n/x) cũng là một ước của n.

Hay nói cách khác nếu một số n đã có 1 ước thì chắc chán sẽ còn 1 ước khác nữa, mà 2 ước này nhân với nhau bằng n, tạm gọi là 2 ước đối số. 2 đối số này chắc chán sẽ có 1 số nhỏ hơn và 1 số lớn hơn căn bậc hai của n, và trong trường hợp n là số Chính phương thì 2 đối số này bằng nhau(16 = 4×4).

• Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
• MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
• Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022

Một số ví dụ cụ thể

với số 20

20 sẽ chia hết cho 2, như vậy 20 cũng sẽ chia hết cho (20/2) tức là 10…và gọi 2 và 10 là cặp ước đối số.

20 cũng chia hết cho 4, như vậy cũng sẽ chia hết cho đối số là 5.

với số 16

16 chia hết cho 2, như vậy 16 cũng sẽ chia hết cho 8

16 chia hết cho 4, mà ước đối số của 4 thì cũng sẽ chính là 4 vì 16 là số chính phương.

Với số 17

sqrt của 17 sẽ rơi vào khoảng là 4.xxx, và số 17 thì không thể chia hết cho các số 2, 3, 4 là các số nhỏ hơn sqrt của 17. Như vậy tức là số 17 chính là số nguyên tố rồi vì không thể nào tồn tại 2 số lớn hơn hoặc bằng 5 nhân với nhau nhỏ hơn 17 được (5 x 5 = 25).

Như vậy, rõ rằng thay vì duyệt vòng lặp chạy từ 1 cho tới n để kiểm tra xem n có chia hết cho i không, thì lúc này chúng ta sẽ rút ngắn vòng lặp chỉ cần chạy từ 1 cho tới căn bậc 2 của n là được rồi. Kiểm tra số 1 tỉ là số nguyên tố hay không thay vì như bên trên chạy 1 tỉ bước lặp thì giờ đây chỉ chạy tới căn bậc 2 của 1 tỉ tức là 31.622 bước lặp…rõ rằng tối ưu hơn rất nhiều lần.

Ta sẽ có hàm kiểm tra số nguyên tố viết lại như sau.

#include <stdio.h>
#include <math.h>
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);
	

	if(checkNT(n) == true) printf("%d la so nguyen to", n);
	else printf("%d khong phai so nguyen to", n);
}

Hàm tính căn bậc sqrt nằm trong thư viện math.h trong C.

Lưu ý một chút là các bạn nên để hàm tính căn bặc 2 ra bên ngoài vòng lặp nhé, nếu để ngay bên trong điều kiện vòng lặp như sau for(int i=2;i <=sqrt(n) ;i++) là mỗi lần thực hiện lại bước lặp chương trình sẽ tính toán căn bậc 2 một lần nữa nên chương trình sẽ chậm hơn đấy.

Cảm ơn bạn đã đọc hết bài viết! Chúc bạn học tốt!@@

[XEM THÊM NHIỀU BÀI VIẾT LẬP TRÌNH C/C++ TẠI ĐÂY]

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ự