Số nguyên tố

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 cũng như khi tham gia vào các cuộc thi 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.

Có rất nhiều dạng phát biểu khác nhau của bài toán nhưng suy cho cùng, các lập trình viên vẫn phải viết một hàm kiểm tra với input là 1 số nguyên n, output là đúng (TRUE – 1) nếu n là một số nguyên tố và sai (FALSE – 0) nếu n không phải là một số nguyên tố. Các thuật toán kiểm tra số nguyên tố mà tôi trình bày với các bạn trong bài viết này chỉ là các thuật toán hết sức đơn giản, nhưng đủ sức đáp ứng cho nhu cầu của các lập trình viên trong các cuộc thi lập trình cũng như những công việc đòi hỏi xử lý những số nguyên không quá lớn.
Trước hết cũng nên nhắc lại khái niệm số nguyên tố (prime number): số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Theo định nghĩa này số nguyên tố là số tự nhiên và chỉ có hai ước số phân biệt, đó chính là số 1 và bản thân nó. Từ đó suy ra số 1 không phải là một số nguyên tố (có rất nhiều sinh viên mới học lập trình nhầm số 1 là số nguyên tố). Một kết quả khác cũng không kém quan trọng được rút ra đó là số 2 là số nguyên tố đầu tiên (nhỏ nhất) và cũng là số nguyên tố chẵn duy nhất.
Như vậy để kiểm tra một số nguyên có là số nguyên tố hay không, theo suy nghĩ trực quan của tất cả các lập trình viên hay thậm chí một người không hiểu biết gì về thuật toán thì chúng ta cần kiểm tra xem số đó có ước số nào khác 1 và chính nó hay không, nếu có thì đó là hợp số (combine number) còn nếu không có số nào thì đó chính là một số nguyên tố. 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 ktnguyento1(int n)
{
 // hàm kiểm tra n có là số nguyên tố hay không
 // kết quả: 1 nếu đúng, 0 nếu sai
 int i;
 int kq = 1; // gia sử n là số nguyên tố
 for(i=2;i
 if(n % i == 0)
 {
  // n có ước số là i, không cần kiểm tra tiếp các giá trị tiếp theo
  kq = 0;
  break;
 }
 return kq;
}

Cài đặt này rất dễ dàng chuyển thành các cài đặt trên các ngôn ngữ khác nhau Pascal, C++ … Tuy nhiên trong ngôn ngữ C khi gặp lệnh return hàm sẽ kết thúc nên cài đặt trên có thể chuyển thành dạng ngắn gọn như sau:

int ktnguyento1(int n)
{
 // hàm kiểm tra n có là số nguyên tố hay không
 // kết quả: 1 nếu đúng, 0 nếu sai
 int i;
 for(i=1;i<=n;i++)
  if(n % i == 0) return 0;
 return 1;
}

Hàm này vẫn chưa đúng hoàn toàn vì khi n = 1 kết quả chạy hàm là: 1 là số nguyên tố vì thế nên cần sửa lại như sau:

int ktnguyento1(int n)
{
// hàm kiểm tra n có là số nguyên tố hay không
// kết quả: 1 nếu đúng, 0 nếu sai
 int i;
 if (n==1)
  return 0;
 for(i=1;i<=n;i++)
  if(n % i == 0) return 0;
 return 1;
}

Một số sinh viên lại cài đặt thuật toán theo kiểu khác như sau:

int ktnguyento0(int n)
{
 // hàm kiểm tra n có là số nguyên tố hay không
 // kết quả: 1 nếu đúng, 0 nếu sai
 int i;
 int dem = 0; // đếm tổng các ước của n
 for(i=1;i<=n;i++)
  if(n % i == 0) dem = dem + i;
 if(dem==n+1) return 1;
 return 0; // tương tự như else return 0;
}

Về cài đặt thì khác nhau nhưng đều là kiểm tra các ước số của n với các ứng cử viên là từ 2 (1) cho tới n-1 (n) và tất nhiên thuật toán kiểu cộng các ước số này sẽ chạy chậm hơn trong đa số các trường hợp. Một số sinh viên lại cài đặt khác đôi chút: thay vì đếm tổng các ước số, ta đếm số các ước số lưu vào biến dem, cuối cùng so sánh biến dem với 2 để kết luận.
Trong các 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 2 sẽ là như sau:

int ktnguyento2(int n)
{
// hàm kiểm tra n có là số nguyên tố hay không
// kết quả: 1 nếu đúng, 0 nếu sai
int i;
 if (n==1)
  return 0;
 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?). Do đó thuật toán mới (3) là như sau:

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

Ở đây chúng ta cần chú ý đôi chút vì nếu chỉ để như trên thì đôi khi chương trình của chúng ta chạy không đúng, lý do là C có hai hàm sqrt để lấy căn bậc hai của một số; hàm thứ nhất là dành cho các số thực kiểu double (hàm này là hàm mà chúng ta dùng ở trên), hàm thứ hai dành cho các số phức, và bình thường nếu không include file math.h thì Turbo C sẽ dùng hàm dành cho các số phức (file complex.h, DevCpp không bị hiện tượng này).
Với cài đặt trên vẫn có thể có cải tiến được (hầu hết các sinh viên và những người mới học lập trình không để ý điều này), đó là thay vì mỗi lần lặp đều tính sqrt(n) ta chỉ cần tính một lần trước khi thực hiện vòng lặp:

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

Thực tế chạy chương trình cho thấy nếu để nguyên cài đặt thuật toán 2 ở trên thì kết quả chạy lại chậm hơn thuật toán 1 vì mỗi bước đều phải thực hiện phép chia đối với n, nên cần phải chỉnh lại cài đặt của thuật toán 2 giống như thuật toán 3: tính m = n/2 trước khi chạy vòng lặp mới đạt được hiệu quả.
Lại để ý rằng 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 (4) sẽ như sau:

int ktnguyento4(int n)
{
int i;
int m;
if(n == 2)
 return 1;
if (n == 1||n % 2 == 0)
 return 0;
m = (int)sqrt(n);
for(i=3;i<=m;i=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 , , ta sẽ bắt đầu với giá trị i = 5 nên sẽ chọn công thức . Nhưng nếu chỉ kiểm tra i sẽ thiếu mất ứng cử viên ở dạng nên ta sẽ kiểm tra thêm giá trị i+2 ( ) cho đủ. Vậy thuật toán mới (5) sẽ là như sau:

int ktnguyento5(int n)
{
 int i;
 int m;
 if(n == 2 || n == 3)
  return 1;
 if (n == 1||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;
}

Cũng có thể cài đặt thuật toán này dựa vào nhận xét sau: nếu ta bắt đầu bằng số i = , thì lần sau sẽ cần cộng i với 2 để kiểm tra giá trị tiếp theo của i (khi đó i sẽ có dạng ), lần sau nữa sẽ cộng i với 4 (để i lại có dạng ), lần tiếp theo lại là 2… Từ nhận xét này dẫn tới cài đặt sau (không hiệu quả hơn cài đặt trên khi chạy trên thực tế):

int ktnguyento51(int n)
{
int i;
int m, y;
if(n == 2 || n == 3)
 return 1;
if (n == 1||n % 2 == 0||n % 3 == 0)
 return 0;
m = (int)sqrt(n);
y = 2;
for(i=5;i<=m;i=i+y, y = 6 - y)
 if(n % i == 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 kiểm tra tính nguyên tố của một số nguyên bằng cách chỉ kiểm tra các ước số có thể có của n nhưng là số nguyên tố, vì nếu n là hợp số thì chắc chắn sẽ chia hết cho một số nguyên tố nào đó nhỏ hơn nó. Vì vậy ta sẽ sinh trước một mảng các số nguyên tố (về bản chất là đánh dấu các số đó là số nguyên tố) không vượt quá giới hạn của n (giá trị lớn nhất của n). Sau đó khi kiểm tra các ước số của n chỉ cần kiểm tra xem n có chia hết cho các số nguyên tố nhỏ hơn căn bậc hai của n nằm trong mảng đã cho hay không. Để làm việc này có một thuật toán nổi tiếng gọi là sàng Erastosthene như sau:

const int MAX_N = 10000; // giá trị lớn nhất của n
int nt[MAX_N]; // mảng đánh dấu, nt[i] = 0 nếu i là số nguyên tố, 1 nếu ngược lại

void sangnt(int n)
{
 // đánh dấu các số nguyên tố nhỏ hơn n
 int i, k;
 for (i=2; i<n; i++)
  if (nt[i] == 0) // nếu i là số nguyên tố thì các bội của i sẽ là hợp số
  {
    k = 2;
    // đánh dấu các bội số của i
    while (k*i<n)
      nt[i*k++] = 1;
  }
}

Kết luận.
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.