Thuật toán kiếm tra số nguyên tố

Trong bài này mình sẽ trình bày thuật toán để kiểm tra một số có phải là số nguyên tố hay không, sau khi giới thiệu xong thuật toán mình sẽ sử dụng ngôn ngữ C++ để giải mẫu cho các bạn. Trước tiên chúng ta tìm hiểu định nghĩa số nguyên tố là gì đã nhé.

1. Số nguyên tố là gì?

Theo định nghĩa của Wikipedia thì số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11, … là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất.

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 – 6 không tồn tại số nào mà 7 chia hết cả.

2. Thuật toán kiểm tra số nguyên tố

Dựa vào định nghĩa của số nguyên tố chúng ta sẽ có một số cách giải như sau (các ví dụ được viết bằng ngôn ngữ C++):

Bài viết này được đăng tại [kiso.vn]

Cách 1: Lặp từng phần tử với bước nhảy 1

Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:

• Bước 1: Nhập vào n
• Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố
• Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

bool laSoNguyenTo1(int n)
{
	// Neu n < 2 thi khong phai la SNT
	if (n < 2){
		return false;
	}		
	
	for (int i = 2; i < (n - 1); i++){
		if (n % i == 0){
			return false;
		}	
	}
	
	return true;
}

Hàm main:

void main()
{
	int n;
	cout << "Nhap so can kiem tra";
	cin >> n;
		
	if (laSoNguyenTo1(n)){
		cout << "La so nguyen to";
	}
	else {
		cout << "Khong phai so nguyen to";
	}
}

Cách 2: Lặp từng phần tử với bước nhảy 2

Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.

bool laSoNguyenTo2(int n)
{
	// Neu n < 2 thi khong phai la SNT
	if (n < 2){
		return false;
	}		
	
	// Neu n = 2 la SNT
	if (n == 2){
		return true;
	}
	
	// Neu n la so chan thi ko phai la SNT
	if (n % 2 == 0){
		return false;	
	}
	
	// Lap qua cac so le
	for (int i = 3; i < (n - 1); i += 2){
		if (n % i == 0){
			return false;
		}	
	}
	
	return true;
}

Hàm main:

void main()
{
	int n;
	cout << "Nhap so can kiem tra";
	cin >> n;
		
	if (laSoNguyenTo2(n)){
		cout << "La so nguyen to";
	}
	else {
		cout << "Khong phai so nguyen to";
	}
}

3. Lời kết

Vẫn còn rất nhiều cách khác nhưng chung quy lại vẫn phải bám vào định nghĩa số nguyên tố là gì. Ví dụ trong vòng lặp điểm dừng sẽ là (n/2) thay vì (n-1) vì theo lý thuyết thì một số không bao giờ chia hết cho số một nửa của nó. Ví dụ số 9 thì số một nửa của nó là số (9 : 2 = 4), như vậy ta chỉ cần kiểm tra các số từ 2,3,4 mà thôi, còn các số 5,6,7,8 chắc chẵn 9 sẽ không chia hết.

for (int i = 3; i <= (n/2); i += 2){
        if (n % i == 0){
                return false;
        }	
}