Số nguyên tố trong list Python: 2 cách tìm cực nhanh

Tìm kiếm số nguyên tố là một trong những bài toán kinh điển nhất khi bắt đầu học lập trình. Bài viết này sẽ hướng dẫn bạn hai phương pháp để tìm và lọc ra các số nguyên tố từ một list cho trước trong Python, bao gồm cách tiếp cận cơ bản và cách tối ưu hóa cho dữ liệu lớn.

💡 Trả lời nhanh: Để tìm số nguyên tố trong một list Python, bạn có thể tạo một hàm kiểm tra bằng cách lặp từ 2 đến căn bậc hai của số đó, sau đó dùng list comprehension [x for x in lst if is_prime(x)] để lọc. Nếu danh sách chứa hàng trăm nghìn phần tử, thuật toán Sàng Eratosthenes sẽ là giải pháp tối ưu hơn về mặt thời gian.

Đề bài

Input: Một danh sách (list) chứa các số nguyên bất kỳ, bao gồm cả số âm, số 0 và số dương (ví dụ: [-5, 0, 1, 2, 3, 4, 15, 17]).

Output: Một danh sách mới chỉ chứa các số nguyên tố xuất hiện trong danh sách đầu vào, giữ nguyên thứ tự gốc (ví dụ: [2, 3, 17]).

Ràng buộc: Cần xử lý mảng đầu vào một cách an toàn, loại bỏ các số không hợp lệ (như số âm, số 0, số 1) và đảm bảo thuật toán không bị quá tải thời gian khi giá trị các phần tử lớn.

Phân tích bài toán lọc số nguyên tố trong list

Bài toán tìm số nguyên tố trong list Python yêu cầu trích xuất các số tự nhiên lớn hơn 1 và chỉ chia hết cho 1 và chính nó từ một danh sách dữ liệu cho trước.

Về bản chất, chúng ta phải giải quyết hai việc: thứ nhất là kiểm tra xem một số nguyên đơn lẻ có phải là số nguyên tố hay không; thứ hai là áp dụng logic đó lên toàn bộ mảng một cách hiệu quả nhất. Định nghĩa toán học yêu cầu số nguyên tố phải lớn hơn 1, do đó ta có thể dễ dàng loại bỏ ngay lập tức các số âm, số 0 và số 1. Phần khó nhất nằm ở việc làm sao để chứng minh một số lớn là nguyên tố mà không cần chia thử cho quá nhiều số.

📌 Góc nhìn thực tế: Trong thực tế, sinh viên năm 1 thường mắc sai lầm là cho vòng lặp chạy từ 2 đến n-1. Điều này rất không cần thiết và dễ gây lỗi Time Limit Exceeded (Quá thời gian) trên các hệ thống chấm điểm tự động. Bạn chỉ cần lặp đến căn bậc hai của số đó là đủ để kết luận.

Giả định

Chúng ta giả định rằng danh sách đầu vào có thể chứa bất kỳ số nguyên nào. Do đó, logic cốt lõi sẽ luôn có bước rào (guard clause) để loại trừ ngay lập tức các số bé hơn 2.

Dựa trên số lượng phần tử và độ lớn của các số trong mảng, chúng ta có hai hướng tiếp cận chính: giải quyết từng phần tử một cách độc lập, hoặc tính toán trước toàn bộ danh sách số nguyên tố có thể xảy ra.

Cách 1: Kiểm tra từng số nguyên tố bằng Trial Division

Cách kiểm tra từng phần tử bằng vòng lặp đến căn bậc hai (Trial Division) phù hợp cho danh sách ngắn và phân tán.

Ý tưởng

Cách tự nhiên nhất là tách logic kiểm tra số nguyên tố ra thành một hàm riêng biệt. Hàm này nhận vào một số n, kiểm tra xem nó có chia hết cho bất kỳ số nào từ 2 đến sqrt{n} hay không. Nếu không, nó là số nguyên tố. Sau khi có hàm này, chúng ta chỉ việc lướt qua từng phần tử trong danh sách và “nhặt” ra những số thỏa mãn điều kiện.

Các bước

1. Định nghĩa hàm is_prime(n):

   • Nếu n = 1, trả về False.

   • Tính giới hạn lặp là căn bậc hai của $n$.

   • Dùng vòng lặp for i chạy từ 2 đến giới hạn lặp. Nếu n chia hết cho i, trả về False.

   • Nếu vòng lặp kết thúc mà không tìm thấy ước nào, trả về True.

2. Tạo một list rỗng result để lưu kết quả.

3. Duyệt vòng lặp qua từng phần tử x trong danh sách gốc lst.

4. Gọi hàm is_prime(x). Nếu đúng, thêm x vào result.

Minh họa tay

Input thử: lst = [1, 2, 3, 4, 5, 9, 11]

• Bước 1: Viết hàm is_prime(n)

• Bước 2 & 3: Duyệt lst:

  • x = 1: is_prime(1) -> False

  • x = 2: is_prime(2) -> True (căn bậc hai của 2 là 1, vòng lặp không chạy, trả về True) -> Thêm 2 vào kết quả

  • x = 3: is_prime(3) -> True -> Thêm 3

  • x = 4: is_prime(4) -> False (chia hết cho 2)

  • x = 5: is_prime(5) -> True -> Thêm 5

  • x = 9: is_prime(9) -> False (chia hết cho 3)

  • x = 11: is_prime(11) -> True -> Thêm 11

• Output: [2, 3, 5, 11]

Đánh giá

• Phù hợp người mới vì: Rất rõ ràng, dễ viết và dễ debug. Việc tách hàm giúp code sạch sẽ hơn.

• Ưu điểm: Xử lý tốt các mảng có chứa những số cực lớn, miễn là số lượng phần tử không quá nhiều. Tiết kiệm bộ nhớ vì không cần tạo thêm mảng phụ nào khác ngoài mảng kết quả.

• Nhược điểm: Nếu danh sách có hàng chục nghìn phần tử và có nhiều số trùng lặp, chương trình sẽ phải tính toán đi tính toán lại rất nhiều lần, làm lãng phí CPU.

• Độ phức tạp: O(K * √M) thời gian / O(K) bộ nhớ (với K là số phần tử của mảng, M là giá trị trung bình/lớn nhất của các phần tử).

Cách 2: Tối ưu tra cứu mảng với Sàng Eratosthenes

Đối với danh sách chứa hàng trăm nghìn phần tử, việc kết hợp Sàng Eratosthenes để tạo mảng đánh dấu (O(1) tra cứu) là giải pháp tối ưu nhất để tránh Time Limit Exceeded.

Ý tưởng

Khác với Cách 1, cách này không kiểm tra độc lập từng số. Thay vào đó, nó tìm số lớn nhất trong danh sách, sau đó dùng thuật toán Sàng Eratosthenes để tạo ra một “bản đồ” (boolean array) đánh dấu sẵn xem tất cả các số từ 2 đến giá trị lớn nhất đó là nguyên tố hay không. Một khi bản đồ được xây dựng xong, việc kiểm tra bất kỳ số nào trong danh sách gốc chỉ mất O(1) thời gian bằng cách tra cứu index.

Các bước

1. Tìm giá trị lớn nhất (max_val) trong danh sách đầu vào lst.

2. Nếu max_val nhỏ hơn 2, tức là danh sách không thể chứa số nguyên tố nào, trả về danh sách rỗng.

3. Tạo một mảng boolean sieve có kích thước max_val + 1, khởi tạo tất cả là True.

4. Thiết lập sieve[0] = sieve[1] = False.

5. Dùng vòng lặp chạy từ 2 đến sqrt{\text{max\_val}}. Nếu sieve[p] là True, thì đánh dấu tất cả các bội số của p là False.

6. Duyệt qua mảng lst gốc. Lọc ra các phần tử x thỏa mãn x >= 2 và sieve[x] là True.

Minh họa tay

Input thử: lst = [1, 2, 3, 4, 5, 9, 11]

• Bước 1: max_val = 11

• Bước 3: Tạo mảng sieve dài 12 phần tử, đều là True.

• Bước 4: sieve[0] = False, sieve[1] = False.

• Bước 5:

  • p = 2: Đánh dấu các bội số (4, 6, 8, 10) thành False.

  • p = 3: Đánh dấu các bội số (9) thành False.

  • (Căn bậc hai của 11 là 3, vòng lặp dừng).

• Bước 6: Duyệt lst:

  • x = 1: Bỏ qua (vì < 2)

  • x = 2: sieve[2] là True -> Nhận

  • x = 3: sieve[3] là True -> Nhận

  • x = 4: sieve[4] là False -> Bỏ

  • x = 5: sieve[5] là True -> Nhận

  • x = 9: sieve[9] là False -> Bỏ

  • x = 11: sieve[11] là True -> Nhận

• Output: [2, 3, 5, 11]

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

Bạn bắt buộc phải dùng Sàng Eratosthenes khi bài toán cho một danh sách có độ dài hàng trăm nghìn hoặc hàng triệu phần tử, nhưng giá trị của các phần tử lại không vượt quá mức 10^7 (khoảng giới hạn an toàn để cấp phát mảng boolean trên RAM máy tính thông thường).

Đánh giá

• Ưu điểm: Tốc độ kinh hoàng khi cần xử lý số lượng phần tử khổng lồ nhờ việc tái sử dụng kết quả (tra cứu O(1)).

• Nhược điểm: Tiêu tốn khá nhiều dung lượng RAM để tạo ra mảng Sàng. Nếu trong list có một phần tử giá trị cực kỳ lớn (ví dụ 10^{12}), máy tính có thể bị treo vì hết bộ nhớ.

• Độ phức tạp: O(M log(log M) + K) thời gian / O(M) bộ nhớ (với M là giá trị lớn nhất trong danh sách, K là số phần tử).

So sánh nhanh 2 cách

Bảng này giúp bạn quyết định nên dùng cách nào mà không cần đọc lại toàn bài.

Code Python tìm số nguyên tố trong list đầy đủ

Cách 1 — Kiểm tra từng số bằng Trial Division:

import math
def is_prime(n):
    """
    Kiểm tra một số nguyên đơn lẻ có phải số nguyên tố hay không.
    Trả về True nếu đúng, ngược lại False.
    """
    if n <= 1:
        return False
    # Chỉ cần lặp đến căn bậc hai của n là đủ để xác định
    limit = math.isqrt(n)
    for i in range(2, limit + 1):
        if n % i == 0:
            return False
    return True
def find_primes_trial_division(lst):
    """
    Tìm và trả về danh sách các số nguyên tố từ mảng đầu vào.
    Sử dụng list comprehension để lọc.
    """
    return [x for x in lst if is_prime(x)]
# --- TEST NHANH (xóa hoặc comment lại trước khi đăng) ---
# assert find_primes_trial_division([-1, 0, 1, 2, 3, 4, 9, 11]) == [2, 3, 11]
# --- Nhập liệu ---
# Lưu ý: giả định input hợp lệ (MUC_DO = trung cấp)
# Ví dụ: [-5, 1, 2, 3, 4, 15, 17]
raw_input = input("Nhập mảng số nguyên, cách nhau bằng khoảng trắng: ")
lst = [int(i) for i in raw_input.split()]
print("Các số nguyên tố tìm được:", find_primes_trial_division(lst))

Cách 2 — Tối ưu bằng Sàng Eratosthenes:

import math
def find_primes_sieve(lst):
    """
    Tìm số nguyên tố trong list sử dụng Sàng Eratosthenes.
    Phù hợp cho mảng có nhiều phần tử, giá trị max không quá lớn.
    """
    if not lst:
        return []
        
    max_val = max(lst)
    
    # Nếu phần tử lớn nhất < 2, chắc chắn không có số nguyên tố nào
    if max_val < 2:
        return []
        
    # Khởi tạo Sàng
    sieve = [True] * (max_val + 1)
    sieve[0] = sieve[1] = False
    
    limit = math.isqrt(max_val)
    for p in range(2, limit + 1):
        if sieve[p]:
            # Đánh dấu các bội số của p là False
            for i in range(p * p, max_val + 1, p):
                sieve[i] = False
                
    # Lọc lại danh sách đầu vào, chú ý loại bỏ số âm và số 0
    return [x for x in lst if x >= 2 and sieve[x]]
# --- TEST NHANH ---
# assert find_primes_sieve([-1, 0, 1, 2, 3, 4, 9, 11]) == [2, 3, 11]
# --- Chạy thử ---
lst = [-1, 0, 1, 2, 3, 4, 9, 11]
print("Các số nguyên tố tìm được:", find_primes_sieve(lst))

Ví dụ chạy thử

Lỗi thường gặp khi tìm số nguyên tố

Lỗi 1: Lầm tưởng số 1 là số nguyên tố

Bạn viết hàm và mảng in ra có chứa số 1, khiến chương trình bị chấm điểm sai (Wrong Answer).

Nguyên nhân: Vì định nghĩa toán học quy định rõ số nguyên tố phải là số tự nhiên lớn hơn 1. Số 1 chỉ có đúng một ước số (là chính nó), trong khi số nguyên tố yêu cầu phải có đúng hai ước số (1 và chính nó). Nếu bạn bỏ qua bước rào if n <= 1: return False, thuật toán sẽ dễ nhận nhầm.

Code sai:

# output sai là: [1, 2, 3]
def is_prime(n):
    for i in range(2, n):
        if n % i == 0: return False
    return True

Code đúng:

# output đúng là: [2, 3]
def is_prime(n):
    if n <= 1: return False # Thêm dòng rào này
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

Lỗi 2: Bị lỗi Time Limit Exceeded do vòng lặp quá dài

Chương trình của bạn chạy hoàn hảo với mảng nhỏ, nhưng khi submit lên hệ thống, bạn nhận được lỗi TLE (Quá thời gian).

Nguyên nhân: Vì bạn lặp từ 2 cho đến sát n-1. Khi mảng có những số nguyên tố khổng lồ (ví dụ 10^9+7), vòng lặp sẽ phải chạy hàng tỷ lần. Trong khi đó, tính chất toán học chứng minh rằng, nếu n không có ước nào trong khoảng từ 2 đến căn bậc hai của nó, thì phần phía sau cũng chắc chắn không có.

Code sai:

# Gây lỗi TLE khi chạy vòng lặp cả tỷ lần
def is_prime(n):
    if n <= 1: return False
    for i in range(2, n): # Lặp quá xa
        if n % i == 0: return False
    return True

Code đúng:

import math
# Rút gọn hàng tỷ lần lặp xuống chỉ còn vài chục nghìn lần
def is_prime(n):
    if n <= 1: return False
    for i in range(2, math.isqrt(n) + 1): # Chỉ lặp đến căn bậc 2
        if n % i == 0: return False
    return True

Lỗi 3: Xóa trực tiếp phần tử trên mảng đang duyệt

Mảng kết quả của bạn bị sót mất vài hợp số, chúng vẫn nằm lỳ trong mảng.

Nguyên nhân: Vì bạn đang cố gắng xóa phần tử (bằng lst.remove()) trực tiếp trên một danh sách đang được chạy qua bằng vòng lặp for. Khi xóa xong, độ dài mảng bị co lại, làm cho chỉ số (index) bị xô lệch, khiến vòng lặp vô tình “nhảy cóc” qua phần tử đứng ngay sau nó.

Code sai:

# output sai là: bỏ sót phần tử
lst = [4, 6, 8]
for x in lst:
    if not is_prime(x):
        lst.remove(x) # Lỗi xô lệch index

Code đúng:

# output đúng là: []
lst = [4, 6, 8]
# Hãy dùng list comprehension để tạo ra mảng mới hoàn toàn
new_lst = [x for x in lst if is_prime(x)]

Lỗi 4: Crash chương trình do IndexError khi dùng Sàng Eratosthenes

Bạn áp dụng Cách 2, chương trình bỗng dưng văng lỗi IndexError: list assignment index out of range hoặc IndexError: list index out of range.

Nguyên nhân: Vì mảng đầu vào của bạn hoàn toàn chỉ chứa các số âm hoặc nhỏ hơn 2 (ví dụ [-1, -5, 0]). Khi đó, hàm max(lst) trả về số âm hoặc số nhỏ hơn 2, làm cho việc khởi tạo kích thước mảng Sàng bị sai hoặc vòng lặp thiết lập sieve[0], sieve[1] trỏ vào khoảng không tồn tại. Bạn bắt buộc phải xử lý riêng biệt các trường hợp danh sách chứa toàn số bé.

Code sai:

# Bị crash khi lst = [-1, 0, 1]
max_val = max(lst)
sieve = [True] * (max_val + 1)
sieve[0] = sieve[1] = False # Lỗi vì độ dài mảng có thể chỉ là 0, 1 hoặc 2

Code đúng:

max_val = max(lst)
# Giải quyết nhanh gọn:
if max_val < 2:
    return [] # Dừng luôn vì không thể có số nguyên tố
sieve = [True] * (max_val + 1)
sieve[0] = sieve[1] = False

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

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

Số nguyên tố là một số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số dương là 1 và chính nó. Các ví dụ điển hình bao gồm 2, 3, 5, 7, 11, v.v. Đây là những “viên gạch cơ bản” cấu tạo nên mọi số tự nhiên thông qua phép nhân.

Tại sao chỉ cần lặp đến căn bậc hai khi kiểm tra số nguyên tố trong list Python?

Nếu một số N là hợp số (không phải nguyên tố), nó chắc chắn có thể được phân tích thành N = a * b. Trong hai thừa số này, chắc chắn phải có ít nhất một thừa số nhỏ hơn hoặc bằng sqrt{N}. Do đó, việc kiểm tra các ước từ 2 đến sqrt{N} là đủ để khẳng định tính chất của N, giúp tiết kiệm hàng tỷ vòng lặp vô ích.

 Làm thế nào để tìm số nguyên tố trong Python một cách dễ nhất?

Cách dễ hiểu nhất là tự định nghĩa một hàm is_prime(n) để kiểm tra từng số bằng vòng lặp từ 2 đến căn bậc hai của nó. Sau đó, dùng kỹ thuật list comprehension kết hợp với hàm vừa tạo để lọc mảng.

Cách tìm số nguyên tố bằng thuật toán Sàng Eratosthenes như thế nào?

Thuật toán Sàng Eratosthenes tạo một mảng boolean đánh dấu các số từ 2 đến giá trị lớn nhất (max). Bắt đầu từ số 2, nó sẽ “gạch bỏ” (chuyển thành False) tất cả các bội số của 2. Tiếp tục như vậy cho số chưa bị gạch tiếp theo (3, 5, 7…). Các số còn lại đánh dấu True cuối cùng chính là số nguyên tố.

 Nên dùng Trial Division hay Sàng Eratosthenes để lấy số nguyên tố trong mảng?

Bạn nên sử dụng Trial Division (chia thử từng phần tử đến căn bậc 2) khi danh sách ngắn hoặc chứa các số khổng lồ (hàng tỷ). Ngược lại, hãy chọn Sàng Eratosthenes nếu mảng có đến hàng triệu phần tử nhưng các giá trị không vượt quá mức cho phép của RAM (thường < 10^7).

Tại sao Sàng Eratosthenes lại tối ưu hơn vòng lặp khi xử lý mảng dài?

Vì Sàng Eratosthenes tính toán trước danh sách nguyên tố và đưa vào một mảng lưu trữ tạm. Do đó, việc tra cứu bất kỳ số nào sau này chỉ tốn thời gian O(1). Vòng lặp truyền thống lại phải lặp lại việc kiểm tra mỗi khi gặp một số, dẫn tới tốn thời gian O(sqrt{M}) cho mỗi số, rất lãng phí với các mảng có nhiều phần tử giống nhau.

Tại sao code đếm số nguyên tố trong mảng Python bị lỗi văng Time Limit?

Code Python báo lỗi quá thời gian thường là do bạn dùng cấu trúc lặp for i in range(2, n) chạy thẳng đến sát n. Khi n có giá trị lên tới hàng triệu hoặc tỷ, vòng lặp thực hiện quá nhiều thao tác dư thừa. Lỗi này khắc phục đơn giản bằng cách đổi cận trên thành hàm căn bậc hai math.isqrt(n) + 1.

Kết luận

Bài toán lọc tìm số nguyên tố từ danh sách đã mang đến cơ hội để bạn làm quen với việc cân bằng giữa thuật toán Trial Division (tiết kiệm bộ nhớ) và Sàng Eratosthenes (tốc độ tuyệt đỉnh). Bạn có thể lựa chọn tùy thuộc vào quy mô của hệ thống. Dù áp dụng cách nào, hãy luôn cẩn thận chặn các trường hợp biên như số âm, số 0 hoặc số 1, đồng thời làm quen với việc sử dụng hàm isqrt để giảm tải cho phần cứ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