Thuật toán tìm số nguyên tố nhanh nhất năm 2024

Thuật toán kiểm tra Số Nguyên Tố

Thuật toán kiểm tra Số Nguyên Tố của một số nguyên dương, cùng với thuật toán tìm UCLN của hai số tự nhiên là những bài toán quan trọng trong Lập trình.

Kiểm tra tính nguyên tố là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.

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

Số nguyên tố [prime] là số tự nhiên lớn hơn 1, chỉ có hai ước số 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.

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

2. Các Thuật toán kiểm tra Số Nguyên Tố Đơn Giản

Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m nằm trong khoảng 2 đến n-1 hay không.

Nếu n chia hết cho một trong các số m nào đó thì n không là số nguyên tố [còn được gọi là hợp số composite]. Ngược lại, nếu n không chia hết cho bất kì số m nào thì kết lianaj n là số nguyên tố.

Thực ra việc kiểm tra với m từ 2 đến n-1 là không cần thiết, mà chỉ cần kiểm tra đến $\sqrt{n}$ là đủ. Vì nếu n là hợp số thì nó chắc chắn có ước số không vượt quá `n`5.

Lặp từng phần tử với bước nhảy 1 đến n-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`8 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ố.

Độ phức tạp của thuật toán trên là $O[n]$.

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.

• Bước 1: Nhập vào n;
• Bước 2: Kiểm tra nếu n`8 thì kết luận `n không phải là số nguyên tố;
• Bước 3: Kiểm tra nếu `n`8 thì kết luận n là số nguyên tố;
• Bước 4: Kiểm tra nếu n`9 và chẵn thì kết luận `n không phải là số nguyên tố;
• Bước 5. Lặp từ m`1 tới `n`1, bước nhảy là `2 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ố.

Lặp từng phần tử đến $\sqrt{n}$

Để tối ưu hơn, thay vì lặp tới n-1, chúng ta chỉ cần lặp các số từ 2 đến n`5, nếu `n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

Độ phức tạp của thuật toán trên là $O[\sqrt{n}]$.

Xem mã nguồn viết bằng ngôn ngữ Dart tại đây //divin.dev/dart/2021/10/14/bai-tap-dart-17.html

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

Chúng ta có thể tối ưu thuật toán trên bằng cách chỉ ra n không chia hết cho những số nguyên tố nhỏ hơn nó. Tuy nhiên, chúng ta lại chưa biết được các số nguyên tố nhỏ hơn nó là những số nào [Bạn có thể sử dụng phương pháp sàng số nguyên tố – Sàng Eratosthenes để tìm ra các số nguyên tố nhỏ hơn số n cho trước]. Nên ta sử dụng kết quả sau đây:

Tất cả những số nguyên tố lớn hơn `m`1 đều có dạng `2`6 [vì `2`7 là những số chẵn; `2`8 thì chia hết cho `m`1].

Do đó, chúng ta chỉ cần kiểm tra các số có dạng n-1`0 từ `2 đến n-1`2, nếu `n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

def is_prime[n: int] -> bool:

"""Primality test using 6k+-1 optimization."""  
if n  1  
if n % 2 == 0 or n % 3 == 0:  
    return False  
i = 5  
while i ** 2