Các thuật toán kiểm tra số nguyên tố – Algorithm check prime number

Có lẽ một trong những bài toán mà tất cả các lập trình viên đều gặp phải khi học lập trình là bài toán kiểm tra một số nguyên có phải là một số nguyên tố hay không.

Thuật toán đầu tiên đến với chúng ta đó là: kiểm tra các số có khả năng là ước số của n (số cần kiểm tra tính nguyên tố), các số này nằm trong khoảng từ 2 tới n – 1. Thuật toán được cài đặt bằng C đơn giản như sau:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i < n; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

Trong cài đặt trên, nếu n là số nguyên tố thì vòng lặp for sẽ chạy tới khi i = n – 1 để có thể đưa ra kết luận cuối cùng. Tuy nhiên, suy nghĩ thêm một chút chúng ta sẽ thấy rằng không cần phải kiểm tra đến giá trị i = n – 1 mà thực chất chỉ cần tới n/2 (n div 2) vì không có ước số nào của n lớn hơn n/2. Vì vậy thuật toán sẽ là như sau:

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

Lại suy nghĩ thêm một chút chúng ta sẽ thấy rằng cũng không cần thiết phải kiểm tra đến giá trị n/2 mà chỉ cần đến căn bậc 2 của n là được (các bạn hãy tính toán một chút để thấy tại sao lại như vậy ). Ta có thuật toán mới: (Lưu ý khai báo thư viện math.h để tính căn)

#include <math.h>

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return 0;
	return 1;
}

Các số nguyên tố chỉ có thể là các số lẻ trừ số 2, và do đó chúng không thể chia hết cho các số chẵn nên ta chỉ cần kiểm tra các ước số (giá trị của i) là số lẻ, do vậy thuật toán tiếp theo sẽ như sau:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;
	if (n < 2)
		return 0;
	if (n == 2)
		return 1;
	if (n % 2 == 0)
		return 0;

	m = (int) sqrt(n);
	for (i = 3; i <= m; i += 2)
		if (n % i == 0)
			return 0;
	return 1;
}

Rõ ràng so với thuật toán trước đó, số giá trị của i cần kiểm tra giảm đi một nửa. Như vậy mấu chốt trong việc tăng tốc và cải tiến thuật toán nằm ở câu lệnh thay đổi giá trị của biến điều khiển i, ta chỉ cần giảm số giá trị của i cần kiểm tra là sẽ dẫn tới một thuật toán hiệu quả hơn.
Vừa rồi ta đã loại bỏ được một nửa số giá trị của i bằng cách xét ước số 2 có thể có của n. Tiếp theo ta sẽ cải tiến thuật toán bằng cách xét ước số nguyên tố tiếp theo có thể có của n là số 3. Nếu n chia hết cho 2 hoặc 3 thì dễ dàng kết luận nó là hợp số (tất nhiên n phải khác hai giá trị đó). Ngược lại n sẽ có ước số có dạng 1+6i,5+6i , ta sẽ bắt đầu với giá trị i = 5. Nhưng nếu chỉ kiểm tra i sẽ thiếu mất ứng cử viên ở dạng 1+6i nên ta sẽ kiểm tra thêm giá trị i+2 (lưu ý: khi ta bắt đầu với i=5 thì ta có i+2 <=> 1+6i) cho đủ. Vậy thuật toán mới (5) sẽ là như sau:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;

	if (n < 2)
		return 0;

	if (n == 2 || n == 3)
		return 1;
	if (n % 2 == 0 || n % 3 == 0)
		return 0;
	
	m = (int) sqrt(n);
	for (i = 5; i <= m; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return 0;
	return 1;
}

Trong các bài toán mà việc kiểm tra số nguyên tố bị lặp lại nhiều lần ta cũng có thể cải thiện thuật toán bằng cách dùng thuật sàng nguyên tố ở đây.

Qua việc trình bày các thuật toán đơn giản để kiểm tra các số nguyên tố nhỏ, tôi hy vọng mang đến cho các bạn một thuật toán tốt để có thể sử dụng trong các cuộc thi lập trình hay các bài toán trong phạm vi nhỏ, đồng thời qua đó minh họa quá trình tinh chỉnh cài đặt một thuật toán. Có thể cùng một thuật toán nhưng với các cài đặt khác nhau, hiệu quả sẽ khác nhau, và nhiều khi hiệu quả đó lại dựa trên những chi tiết tưởng chừng như rất nhỏ nhặt, không đáng lưu tâm.

Nếu có thuật toán nào tốt, hay, tối tưu rất mong các bạn chia sẻ để chúng ta cùng thảo luận, học tập thêm.

Bài viết gốc / Source: vietsource.net