Thuật toán kiểm tra số nguyên tố (Phần 1)

Có thể bạn thích

Số nguyên tố được xem là trung tâm của lý thuyết số trong Toán học. Việc kiểm định một số nguyên tố luôn là vấn đề nan giải đối với các nhà khoa học nhưng lại là một trong những vấn đề vô cùng hấp dẫn khiến cho việc tìm kiếm và phát minh ra các phương pháp mới để kiểm tra số nguyên tố ngày càng tối ưu và hiệu quả.
Ngày nay, với sự trợ giúp đắc lực của máy tính điện tử, người ta đã tìm ra được số nguyên tố lớn nhất (là số nguyên tố lớn nhất được tìm thấy cho đến hiện tại, có thể vẫn còn một số nguyên tố lớn hơn nhưng vẫn chưa được tìm thấy) có 23 triệu chữ số và có độ dài hơn 118 km nếu viết 2 chữ số trên 1cm, tính đến tháng 12 năm 2018. Việc tìm kiếm này đã được thực hiện trên một "siêu máy tính" dựa trên thuật toán Mersenne.

Trong bài viết này, mục tiêu của chúng ta là sẽ đi tìm hiểu các phương pháp kiểm tra số nguyên tố, từ đơn giản đến phức tạp, để xem các phương pháp này đã có bước phát triển như thế nào.

Nhắc lại kiến thức cơ bản

Theo kiến thức phổ thông, số nguyên tố là số lớn hơn 1 và không được tạo thành từ việc nhân hai số tự nhiên nhỏ hơn lại với nhau.

Định nghĩa ở trên có thể được phát biểu đơn giản như sau: Số nguyên tố là số lớn hơn 1, chỉ chia hết cho 1 và chia hết cho chính nó.

Ngoài ra vẫn còn một định nghĩa về hợp số có tính chất trái ngược với số nguyên tố.

Như vậy, số 0 và 1 không được xem là số nguyên tố, cũng không được xem là hợp số, vì vậy khi thực hiện kiểm tra số nguyên tố, chúng ta sẽ loại bỏ 2 trường hợp này như là điều tất yếu.

Tiếp theo, chúng ta sẽ đi tìm hiểu các phương pháp kiểm tra số nguyên tố, bắt đầu bằng phương pháp vô cùng cơ bản.

Phương pháp cổ điển (phương pháp chân phương)

Đây là phương pháp đơn giản nhất, được suy ra trực tiếp từ định nghĩa về số nguyên tố.

Chúng ta thực hiện việc kiểm tra một số nguyên tố bằng cách kiểm tra phép chia lấy dư của số n trong khoảng từ [2, n - 1].

Phương pháp này tuy dễ hiểu và dễ cài đặt nhưng lại rất chậm và không được tối ưu.

Từ phương pháp trên, chúng ta có thể tối ưu chúng một chút bằng cách giảm số vòng lặp với các phương pháp sau:

• Chỉ cần kiểm tra trong đoạn [2, sqrt(n)].
• Thực hiện việc chia lấy dư với các số nguyên tố được cài đặt sẵn (đã được xác nhận là chính xác).

Chúng ta có thể chỉ áp dụng phương pháp đầu tiên hoặc kết hợp cả hai phương pháp trên.

Để có thể áp dụng được phương pháp thứ hai đòi hỏi máy tính cần có một bộ nhớ lớn để lưu trữ các số nguyên tố sẵn có. Việc này tuy nhanh vì có thể giảm được vòng lặp cho thuật toán xuống mức tối thiểu nhưng lại khá tốn bộ nhớ, chỉ thích hợp nếu bạn muốn tăng tốc độ thuật toán cho các giá trị lớn.
Dưới đây mình sẽ mô tả thuật toán cho hai phương pháp trên như sau:

Trường hợp 1: Chỉ áp dụng phương pháp đầu tiên.

Trường hợp 2: Áp dụng cả 2 phương pháp.

Ở đây có thể thực hiện thêm thao tác thêm giá trị nguyên tố mới vào mảng để kiểm tra những số nguyên tố lớn hơn.

Câu hỏi được đặt ra là tại sao chúng ta có thể đem n chia cho những số nguyên tố sẵn có nhỏ hơn mà không cần xét các trường hợp hợp số khác? Phương pháp này dựa trên kiến thức phổ thông đã được học, bất kì số tự nhiên lớn hơn 1 nào cũng đều có thể phân tích thành tích của các thừa số nguyên tố. Do đó chỉ việc đem n chia cho các giá trị nguyên tố sẵn có, nếu tồn tại một số nguyên tố nhỏ hơn n mà n chia hết thì số đó là hợp số.

Trường hợp ngoài lề: Phương pháp 6k ± 1

Phương pháp này được dựa trên một tính chất của số nguyên tố. Tính chất này được phát biểu như sau: Với mọi số nguyên tố (ngoại trừ 2, 3), chúng ta đều có thể biểu diễn chúng dưới dạng của biểu thức 6k ± 1.

Kết luận

Trên đây là những phương pháp kiểm tra số nguyên tố cơ bản nhất. Ở phần 2 sẽ là một "chân trời mới", vì những phương pháp ở phần 2 tương đối phức tạp và khó cài đặt.

Happy coding!

Thanh Dương