Cách kiểm tra số nguyên tố Python: 2 Thuật toán tối ưu

Bài viết này sẽ hướng dẫn bạn chi tiết cách viết hàm kiểm tra số nguyên tố trong Python, từ phương pháp cơ bản nhất đến các kỹ thuật tối ưu hóa dành cho dữ liệu lớn. Sau khi đọc xong, bạn không chỉ biết cách code mà còn hiểu rõ bản chất toán học đằng sau để áp dụng vào các bài toán phân tích thuật toán thực tế.

💡 Trả lời nhanh: Để kiểm tra một số n có phải là số nguyên tố hay không một cách tối ưu, hãy loại bỏ các trường hợp n < 2, sau đó dùng vòng lặp for duyệt từ 2 đến math.isqrt(n) + 1. Nếu n chia hết cho bất kỳ số nào trong khoảng này, nó không phải là số nguyên tố. Hàm math.isqrt() trong Python 3.8+ giúp tránh sai số dấu phẩy động hoàn hảo.

Đề bài 

Yêu cầu cốt lõi của bài toán là xây dựng một hàm logic để xác định tính chất nguyên tố của một số nguyên cho trước.

Input: Một số nguyên n bất kỳ (có thể là số âm, số 0, hoặc số dương rất lớn).

Output: Giá trị boolean True nếu n là số nguyên tố, ngược lại trả về False.

Ràng buộc: Thuật toán cần tối ưu về mặt thời gian thực thi, không sử dụng phương pháp chia thử cạn kiệt (brute-force) đến n-1 vì sẽ gây tràn thời gian (Time Limit Exceeded) với các số lớn. Không có giới hạn cụ thể về bộ nhớ, nhưng nên duy trì ở mức độ phức tạp không gian thấp nhất.

Phân tích thuật toán kiểm tra số nguyên tố 

Để kiểm tra số nguyên tố trong Python, phương pháp tối ưu và phổ biến nhất là duyệt các số từ 2 đến căn bậc hai của số đó, vì mọi ước số luôn tồn tại thành từng cặp. Một số nguyên tố được định nghĩa là số tự nhiên lớn hơn 1, chỉ có đúng hai ước số dương là 1 và chính nó. Điều này có nghĩa là mọi số nhỏ hơn 2 (bao gồm số âm, 0 và 1) mặc định không phải là số nguyên tố.

Khi đối mặt với bài toán này, phản xạ đầu tiên của nhiều người là duyệt một vòng lặp từ 2 đến n-1. Nếu n chia hết cho bất kỳ số nào trong khoảng này, thì n không phải là số nguyên tố. Tuy nhiên, cách làm này có độ phức tạp thời gian là O(n), trở nên vô cùng chậm chạp khi n lên tới hàng tỷ. Về mặt toán học, nếu một số n không phải là số nguyên tố, nó có thể được phân tích thành tích của hai thừa số a và b. Chắc chắn ít nhất một trong hai thừa số này phải nhỏ hơn hoặc bằng căn bậc hai của n.

📌 Góc nhìn thực tế: Trong thực tế giảng dạy, sinh viên năm 2 thường mất điểm ở các bài kiểm tra hiệu năng do vẫn dùng vòng lặp range(2, n) hoặc xử lý sai giới hạn vòng lặp khi sử dụng căn bậc hai, dẫn đến sai số với các số chính phương.

Giả định

Trong phạm vi bài viết này, chúng ta giả định đầu vào n luôn là kiểu số nguyên hợp lệ (int). Nếu hệ thống yêu cầu xử lý chuỗi nhập vào từ bàn phím, chúng ta sẽ ép kiểu một cách an toàn nghiệm ngặt.

Chính vì bài toán yêu cầu sự tối ưu, chúng ta sẽ bỏ qua cách giải brute-force ngây thơ và đi thẳng vào 2 phương pháp chuẩn mực nghiệp vụ nhất. Đó là giới hạn vòng lặp ở căn bậc hai và sử dụng bước nhảy thông minh.

Cách giải 1: Thuật toán kiểm tra bằng căn bậc 2 

Cách tiếp cận đầu tiên dựa trên nguyên lý chặn trên của các ước số, giúp giảm thiểu đáng kể số lần lặp mà CPU phải thực hiện.

Ý tưởng cốt lõi

Thay vì kiểm tra xem n có chia hết cho mọi số nhỏ hơn nó hay không, ta chỉ cần kiểm tra đến giá trị phần nguyên căn bậc hai của n. Nếu không tìm thấy bất kỳ ước số nào trong khoảng từ 2 đến sqrt{n}, ta có thể khẳng định chắc chắn rằng không có ước số nào tồn tại ở nửa khoảng lớn hơn sqrt{n}. Nhờ đó, bài toán được thu gọn không gian tìm kiếm một cách triệt để.

Các bước triển khai

1. Kiểm tra điều kiện đầu tiên: Nếu n < 2, lập tức trả về False vì chúng không thể là số nguyên tố theo đúng định nghĩa toán học.

2. Tính giá trị giới hạn trên: Lấy phần nguyên căn bậc hai của n. Trong Python 3.8 trở lên, chúng ta dùng hàm math.isqrt(n).

3. Tạo vòng lặp duyệt biến i chạy từ 2 đến giới hạn trên (nhớ cộng thêm 1 vào cận trên của hàm range để bao gồm cả giá trị căn bậc hai).

4. Trong mỗi lần lặp, dùng phép chia lấy phần dư n % i. Nếu kết quả bằng 0, tức là n chia hết cho i, lập tức trả về False.

5. Nếu vòng lặp kết thúc mà không phát hiện phép chia hết nào, trả về True.

Minh họa tay

Giả sử chúng ta cần kiểm tra n = 29:

• Bước 1: 29 < 2 là sai, bỏ qua.

• Bước 2: Căn bậc hai của 29 khoảng 5.38. Dùng math.isqrt(29) ta được giá trị phần nguyên là 5.

• Bước 3: Vòng lặp i sẽ chạy các giá trị 2, 3, 4, 5.

• Bước 4:

  • 29 % 2 = 1 (khác 0)

  • 29 % 3 = 2 (khác 0)

  • 29 % 4 = 1 (khác 0)

  • 29 % 5 = 4 (khác 0)

• Bước 5: Vòng lặp kết thúc an toàn, hàm trả về True. 29 là số nguyên tố.

Đánh giá thuật toán

• Phù hợp người mới vì: Logic trực quan, dễ hiểu, là bước đệm tuyệt vời để làm quen với việc tối ưu hóa thuật toán căn bản. Thuật toán kiểm tra tới căn bậc hai giúp giảm độ phức tạp từ O(n) xuống O(\sqrt{n}), là lựa chọn an toàn cho mọi bài tập đại cương.

• Ưu điểm: Cải thiện tốc độ chạy hàng nghìn lần so với cách duyệt truyền thống khi n lớn. Code ngắn gọn, ít biến phụ.

• Nhược điểm: Vẫn còn thực hiện một số phép chia thừa. Ví dụ, sau khi đã kiểm tra n không chia hết cho 2, vòng lặp vẫn kiểm tra việc chia cho 4, 6, 8... (điều này hoàn toàn vô nghĩa vì không chia hết cho 2 thì chắc chắn không chia hết cho các số chẵn khác).

• Độ phức tạp: O(\sqrt{n}) thời gian / O(1) bộ nhớ.

Cách giải 2: Tối ưu với bước nhảy 6k ± 1

Khác với Cách 1, cách này loại bỏ hoàn toàn các phép tính dư thừa đối với các bội số của 2 và 3, đẩy tốc độ xử lý lên mức tối đa có thể cho một thuật toán đơn luồng.

Ý tưởng cốt lõi

Quan sát tập hợp các số nguyên, ta thấy mọi số nguyên đều có thể biểu diễn dưới dạng 6k, 6k+1, 6k+2, 6k+3, 6k+4, hoặc 6k+5 (với k là số tự nhiên).

• 6k, 6k+2, 6k+4 đều là số chẵn (chia hết cho 2).

• 6k+3 chia hết cho 3.

  Do đó, mọi số nguyên tố lớn hơn 3 bắt buộc phải nằm ở dạng 6k+1 hoặc 6k-1 (tương đương 6k+5). Kỹ thuật tối ưu 6k ± 1 bỏ qua tất cả các bội số của 2 và 3, giúp tăng tốc độ kiểm tra lên gấp 3 lần khi xử lý số cực lớn.

Các bước triển khai

1. Xử lý nhanh các trường hợp cơ sở: Nếu n <= 1, trả về False. Nếu n == 2 hoặc n == 3, trả về True.

2. Lọc bội số chung: Nếu n chia hết cho 2 hoặc 3, lập tức trả về False.

3. Khởi tạo biến lặp i = 5.

4. Mở vòng lặp while với điều kiện i * i <= n.

5. Trong mỗi vòng lặp, kiểm tra xem n có chia hết cho i hoặc i + 2 hay không. Nếu có, trả về False.

6. Tăng i thêm 6 (i += 6) để chuyển sang cặp số dạng 6k \pm 1 tiếp theo.

7. Nếu thoát khỏi vòng lặp, trả về True.

Minh họa tay

Vẫn với ví dụ n = 29:

• Bước 1 & 2: 29 không nhỏ hơn bằng 1, không phải 2 hoặc 3. 29 không chia hết cho 2, cũng không chia hết cho 3.

• Bước 3: Bắt đầu vòng lặp với i = 5.

• Bước 4: Kiểm tra 5 * 5 <= 29 (tức là 25 <= 29 -> Đúng).

• Bước 5: 29 % 5 = 4 (khác 0), 29 % (5 + 2) tức là 29 % 7 = 1 (khác 0).

• Bước 6: Cập nhật i = 5 + 6 = 11.

• Bước 4 (lần 2): Kiểm tra 11 * 11 <= 29 (tức là 121 <= 29 -> Sai). Vòng lặp kết thúc.

• Bước 7: Hàm trả về True.

Khi nào nên dùng Cách 2?

Phương pháp này là “vũ khí” bắt buộc phải có khi bạn tham gia các nền tảng Lập trình thi đấu (Competitive Programming) như LeetCode, Codeforces, hoặc khi xây dựng các hệ thống mã hóa yêu cầu sàng lọc số nguyên tố với tần suất hàng triệu lần mỗi giây.

Đánh giá thuật toán

• Ưu điểm: Giảm được 2/3 lượng phép toán chia lấy dư so với cách dùng căn bậc hai thông thường. Xử lý các test case lớn cực kỳ mượt mà.

• Nhược điểm: Cấu trúc code phức tạp hơn, có thể khó nhớ với người mới bắt đầu lập trình. Cần cẩn thận với lỗi off-by-one ở vòng lặp while.

• Độ phức tạp: O(\sqrt{n}) thời gian (nhưng số phép tính thực tế ít hơn hẳn) / O(1) bộ nhớ.

So sánh nhanh 2 cách 

Bảng này giúp bạn quyết định nên dùng phương pháp nào để viết hàm kiểm tra số nguyên tố bằng Python mà không cần đọc lại toàn bộ bài phân tích.

Code Python kiểm tra số nguyên tố đầy đủ 

Cách 1 — Thuật toán kiểm tra bằng căn bậc 2:

# Nhập thư viện math để sử dụng hàm isqrt an toàn
import math
def is_prime_basic(n: int) -> bool:
    """
    Hàm kiểm tra số nguyên tố n bằng phương pháp duyệt đến căn bậc hai.
    Nhận vào số nguyên n, trả về True nếu là nguyên tố, False nếu ngược lại.
    """
    # Loại trừ ngay các số nhỏ hơn 2
    if n < 2:
        return False
        
    # Tính phần nguyên căn bậc hai của n
    # Lưu ý: phải cộng 1 trong hàm range để duyệt đến đúng giá trị căn
    limit = math.isqrt(n)
    for i in range(2, limit + 1):
        if n % i == 0:
            return False
            
    return True
# --- TEST NHANH ---
# assert is_prime_basic(29) == True
# assert is_prime_basic(-5) == False
# assert is_prime_basic(9) == False
# --- Nhập liệu (Giả định input hợp lệ) ---
if __name__ == "__main__":
    so_can_kiem_tra = int(input("Nhập một số nguyên: "))
    if is_prime_basic(so_can_kiem_tra):
        print(f"{so_can_kiem_tra} là số nguyên tố.")
    else:
        print(f"{so_can_kiem_tra} không phải là số nguyên tố.")

Cách 2 — Tối ưu với bước nhảy 6k ± 1:

# Điểm khác với Cách 1: Loại bỏ bội của 2 và 3, duyệt với bước nhảy lớn hơn.
def is_prime_optimized(n: int) -> bool:
    """Hàm kiểm tra số nguyên tố cực nhanh dùng tính chất 6k ± 1."""
    # Xử lý các trường hợp cơ sở
    if n <= 1:
        return False
    if n <= 3:
        return True
        
    # Loại bỏ sớm bội số của 2 và 3
    if n % 2 == 0 or n % 3 == 0:
        return False
        
    # Khởi tạo bước nhảy
    i = 5
    while i * i <= n:
        # Kiểm tra i (dạng 6k-1) và i+2 (dạng 6k+1)
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
        
    return True
# --- TEST NHANH ---
# assert is_prime_optimized(29) == True
# assert is_prime_optimized(121) == False
if __name__ == "__main__":
    so_can_kiem_tra = int(input("Nhập một số nguyên: "))
    print(f"Kết quả kiểm tra tối ưu: {is_prime_optimized(so_can_kiem_tra)}")

Ví dụ chạy thử 

Lỗi thường gặp khi viết hàm kiểm tra số nguyên tố 

Lỗi 1: Sai biên vòng lặp với số chính phương

Hiện tượng cực kỳ phổ biến là hàm trả về True với số 9, 25, hoặc 49 thay vì False như mong đợi. Nguyên nhân sâu xa là do hàm range(start, stop) trong Python không bao gồm giá trị stop. Khi bạn dùng range(2, math.isqrt(9)), vòng lặp sẽ tính cận trên là 3, do đó chỉ chạy cho mỗi giá trị i = 2 và dừng lại trước khi kịp kiểm tra số 3.

Code sai:

import math
def check_prime(n):
    # output sai là: check_prime(9) -> True
    for i in range(2, math.isqrt(n)): 
        if n % i == 0: return False
    return n > 1

Code đúng:

import math
def check_prime(n):
    # output đúng là: check_prime(9) -> False
    # Phải cộng 1 để chạy tới đúng giá trị căn bậc hai
    for i in range(2, math.isqrt(n) + 1): 
        if n % i == 0: return False
    return n > 1

Lỗi 2: Bỏ quên việc chặn số âm, 0 và 1 ngay từ đầu

Hiện tượng là code chạy bị treo, ném ra lỗi toán học, hoặc hàm vô tình khẳng định -7 hay 1 là số nguyên tố. Nguyên nhân là do lập trình viên chỉ tập trung vào việc tìm ước số mà quên mất định nghĩa nền tảng: số nguyên tố bắt buộc phải lớn hơn 1. Nếu không có lớp bảo vệ đầu tiên, các logic vòng lặp phía sau có thể hoạt động sai lệch hoàn toàn.

Code sai:

def is_prime(n):
    # output sai là: is_prime(1) -> True
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True # Trả về luôn mà không biết n là mấy

Code đúng:

def is_prime(n):
    # output đúng là: is_prime(1) -> False
    if n < 2: return False # Chặn đứng ở đây
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

Lỗi 3: Dùng float để tính căn bậc hai gây sai số

Hiện tượng xảy ra khi kiểm tra các số cực kỳ lớn (thường vượt qua giới hạn $2^{53}$), hàm bắt đầu đánh giá sai lệch, báo số nguyên tố thành hợp số hoặc ngược lại. Nguyên nhân vì n**0.5 hoặc math.sqrt(n) đều trả về kiểu dữ liệu số thực dấu phẩy động (float). Số float trong hệ thống máy tính có giới hạn độ chính xác. Khi số nguyên quá lớn, giá trị căn bậc hai làm tròn bị sai, dẫn tới vòng lặp chạy thiếu vòng hoặc thừa vòng.

Code sai:

# output sai có thể xảy ra với số khổng lồ
limit = int(n**0.5) + 1 
for i in range(2, limit):
    ...

Code đúng:

import math
# output đúng là: dùng math.isqrt để luôn trả về số nguyên int chính xác
limit = math.isqrt(n) + 1
for i in range(2, limit):
    ...

Lỗi 4: Return bên trong vòng lặp sai logic

Hiện tượng là hàm luôn trả về True ngay cả khi số đó là hợp số (chẳng hạn số 15). Nguyên nhân vì bạn đã đặt câu lệnh return True bên trong khối else của lệnh if n % i == 0, hoặc đặt sai thụt lề (indentation). Điều này khiến vòng lặp chỉ kiểm tra đúng giá trị i = 2 đầu tiên, thấy không chia hết là thoát hàm và khẳng định luôn đó là số nguyên tố.

Code sai:

def check(n):
    # output sai là: check(15) -> True vì 15 không chia hết cho 2
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
        else:
            return True # Sai lầm chết người

Code đúng:

def check(n):
    # output đúng là: check(15) -> False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    # Chỉ return True khi đã chạy xong toàn bộ vòng lặp an toàn
    return True

Lỗi 5: Đặt tên hàm trùng với biến toàn cục hoặc từ khóa

Hiện tượng là chương trình báo lỗi TypeError: 'bool' object is not callable hoặc các thông báo kỳ lạ khác khi bạn gọi hàm. Nguyên nhân do bạn vô tình đặt tên một biến chứa kết quả trùng với tên hàm bạn vừa định nghĩa (ví dụ: is_prime = is_prime(10)). Khi đó Python ghi đè tham chiếu của hàm thành một giá trị boolean tĩnh, nên các lần gọi hàm sau đó sẽ bị crash.

Code sai:

def is_prime(n): ...
# output sai: Lỗi TypeError ở dòng thứ 2
is_prime = is_prime(17) 
print(is_prime(19)) 

Code đúng:

def is_prime(n): ...
# output đúng là: Đặt tên biến nhận kết quả phân biệt rõ ràng
result = is_prime(17)
print(is_prime(19))

Câu hỏi thường gặp 

Thế nào là thuật toán kiểm tra số nguyên tố tối ưu nhất trong Python?

Thuật toán kiểm tra số nguyên tố tối ưu nhất không dựa trên các module viết sẵn, mà dựa vào kỹ thuật nhảy bước 6k ± 1. Bằng cách bỏ qua hoàn toàn các bội số chẵn của 2 và 3, kết hợp với việc giới hạn không gian tìm kiếm ở căn bậc hai của n, thuật toán này hoạt động với độ phức tạp thời gian gần như hoàn hảo cho môi trường đơn luồng.

Hàm math.isqrt() khác gì so với math.sqrt() khi kiểm tra số nguyên tố?

Hàm math.sqrt() luôn trả về giá trị kiểu số thực (float), điều này có thể gây ra sai số nghiêm trọng khi xử lý các số nguyên quá lớn do giới hạn bộ nhớ dấu phẩy động. Trong khi đó, math.isqrt() ra mắt từ Python 3.8 trả về kết quả cắt tỉa phần thập phân dưới dạng số nguyên (int), đảm bảo sự chính xác tuyệt đối và an toàn cho vòng lặp duyệt số nguyên tố.

Làm thế nào để in ra danh sách các số nguyên tố trong Python?

Nếu bạn muốn tìm tất cả các số nguyên tố trong một giới hạn nhất định thay vì kiểm tra một số đơn lẻ, bạn không nên gọi hàm kiểm tra lặp đi lặp lại. Cách giải Python chuẩn xác và nhanh nhất cho dạng bài này là sử dụng thuật toán Sàng Eratosthenes (Sieve of Eratosthenes). Thuật toán này dùng một danh sách boolean để đánh dấu bội số, thay vì làm phép chia phức tạp.

Có thư viện Python nào tích hợp sẵn hàm kiểm tra số nguyên tố không?

Thư viện chuẩn của Python không có sẵn hàm is_prime(). Tuy nhiên, nếu bạn sử dụng thư viện toán học nâng cao mã nguồn mở SymPy, bạn có thể dùng trực tiếp hàm sympy.isprime(n). Thư viện này đã tối ưu hóa các phép thử số nguyên tố Miller-Rabin bên dưới nền, cực kỳ phù hợp cho các nghiên cứu đại số.

Nên dùng cách chia cho căn bậc hai hay dùng Sàng Eratosthenes để kiểm tra số nguyên tố?

Điều này hoàn toàn phụ thuộc vào mục đích của bạn. Nếu bạn chỉ cần xác định tính chất của một (hoặc vài) số n cụ thể được nhập vào, phương pháp căn bậc hai bằng cách lặp for là phù hợp và tốn ít bộ nhớ nhất. Nhưng nếu bài toán yêu cầu truy vấn liên tục “số X có phải số nguyên tố không” hàng nghìn lần trong mảng, bạn phải dùng Sàng Eratosthenes để tạo bảng tra cứu trước (pre-computation).

Tại sao code kiểm tra thuật toán số nguyên tố của tôi lại chạy quá thời gian (TLE) trên LeetCode?

Lỗi Time Limit Exceeded (TLE) xảy ra chủ yếu vì bạn đang dùng vòng lặp for i in range(2, n) để đếm ước số nghiệm ngặt. Khi hệ thống chấm nghiệm với test case n = 10^9, số phép tính trở nên khổng lồ đối với Python. Việc bạn cần làm là thay đổi cận trên của vòng lặp thành căn bậc hai của n, số vòng lặp sẽ lập tức giảm từ 1 tỷ xuống chỉ còn khoảng 31 nghìn vòng.

Tại sao code Python lại không nhận số âm là số nguyên tố?

Định nghĩa quy ước của toán học về số nguyên tố khẳng định rằng chúng phải là các số tự nhiên lớn hơn 1 và chỉ có 2 ước số dương. Số âm có nhiều hơn 2 ước số nếu xét trên tập số nguyên (ví dụ -5 chia hết cho 1, -1, 5, -5). Do đó, việc code Python trả về False khi nhập các giá trị nhỏ hơn 2 là hoàn toàn chuẩn xác về mặt toán học.

Kết luận

Kiểm tra số nguyên tố là một kỹ năng lập trình bắt buộc mà bất kỳ sinh viên nào cũng phải nắm vững để xử lý các bài toán cấu trúc dữ liệu. Nếu bạn chỉ làm các bài tập môn học cơ bản với giới hạn dữ liệu nhỏ, phương pháp duyệt đến căn bậc hai là đủ để đáp ứng độ tin cậy.

Tuy nhiên, khi bạn dấn thân vào con đường lập trình thi đấu hoặc xây dựng hệ thống thật, hãy luôn nhớ mang theo “vũ khí” bước nhảy 6k ± 1 để tối ưu hóa hiệu năng ứng dụng.

Các khóa học liên quan: 

• Làm chủ Python trong 4 tuần

• Học python căn bản thông qua lập trình 1 game

• Python Excel cho người đi làm

• Học lập trình Python cho mọi lứa tuổi

• Thành thạo xử lý dữ liệu với Python

• Tập làm kĩ sư Amazon vận hành robot nông nghiệp với Python

Một số sản phẩm từ Python:

• Tool MMO: “Máy xay clip” chuẩn MMO cho TikTok, YouTube Shorts, Facebook Reels

Một số sách lập trình Python bạn hãy tham khảo

• Tiki: Python
• Shopee: Pyhon