Kiểm Tra Số Nguyên Tố Python: 5 Cách Viết Code Đơn Giản & Tối Ưu Nhất

Trong lập trình, việc xử lý các bài toán liên quan đến số học luôn đóng vai trò quan trọng, đặc biệt là khi làm việc với thuật toán và tối ưu hiệu năng. Một trong những bài toán cơ bản nhưng rất phổ biến là kiểm tra số nguyên tố – nền tảng cho nhiều ứng dụng như mã hóa, bảo mật và xử lý dữ liệu. Với ngôn ngữ Python, bạn có thể triển khai bài toán này theo nhiều cách khác nhau, từ đơn giản đến tối ưu. Trong bài viết này, APTECH SAIGON sẽ hướng dẫn chi tiết cách kiểm tra số nguyên tố Python thông qua nhiều phương pháp dễ hiểu và hiệu quả.

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

Số nguyên tố là một khái niệm cơ bản trong toán học, dùng để chỉ những số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số là 1 và chính nó. Nói cách khác, một số được gọi là số nguyên tố nếu nó không thể chia hết cho bất kỳ số nào khác ngoài 1 và chính nó. Đây là nền tảng quan trọng trong nhiều thuật toán lập trình, đặc biệt khi làm việc với các bài toán liên quan đến số học.

Đặc điểm của số nguyên tố:

• • Là số nguyên dương lớn hơn 1
  • Chỉ chia hết cho 1 và chính nó
  • Không thể biểu diễn dưới dạng tích của hai số tự nhiên nhỏ hơn

Ví dụ, các số như 2, 3, 5, 7, 11 là những số nguyên tố vì chúng chỉ có đúng hai ước số là 1 và chính nó:

• • 2 chỉ chia hết cho 1 và 2
  • 3 chỉ chia hết cho 1 và 3
  • 5 chỉ chia hết cho 1 và 5

Ngược lại, các số như 4, 6, 8, 9 không phải là số nguyên tố vì chúng có nhiều hơn hai ước số:

• • 4 chia hết cho 1, 2 và 4
  • 6 chia hết cho 1, 2, 3 và 6
  • 9 chia hết cho 1, 3 và 9

Một số trường hợp đặc biệt cần lưu ý:

• • Số 1 không phải là số nguyên tố vì chỉ có một ước số
  • Số 0 và các số âm cũng không được coi là số nguyên tố.

Tư duy kiểm tra số nguyên tố trong Python

Để giải quyết bài toán kiểm tra số nguyên tố Python, bạn không chỉ cần nắm định nghĩa mà còn phải hiểu rõ cách tư duy kiểm tra một số có thỏa điều kiện hay không. Dưới đây là những nguyên tắc quan trọng giúp bạn xây dựng thuật toán kiểm tra số nguyên tố một cách chính xác và tối ưu:

Thuật toán kiểm tra số nguyên tố cơ bản

Thuật toán kiểm tra số nguyên tố cơ bản là cách đơn giản nhất để xác định một số có phải là số nguyên tố hay không. Ý tưởng chính của phương pháp này là kiểm tra xem số đó có chia hết cho bất kỳ số nào ngoài 1 và chính nó hay không.

Cách thực hiện:

• • Nếu số n < 2 → kết luận ngay không phải số nguyên tố
  • Nếu n ≥ 2 → tiến hành kiểm tra các số từ 2 đến n – 1
  • Nếu tồn tại một số i trong khoảng này mà n chia hết cho i → n không phải số nguyên tố
  • Nếu không tìm thấy số nào chia hết → n là số nguyên tố

Ví dụ, với n = 7:

• • Kiểm tra lần lượt các số 2, 3, 4, 5, 6
  • Không có số nào chia hết cho 7 → kết luận 7 là số nguyên tố

Ngược lại, với n = 9:

• • Kiểm tra đến i = 3, ta có 9 % 3 = 0
  • Kết luận 9 không phải là số nguyên tố

Phương pháp này rất dễ hiểu và phù hợp với người mới bắt đầu, tuy nhiên nhược điểm là phải kiểm tra nhiều lần lặp, dẫn đến hiệu suất không cao khi làm việc với các số lớn.

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

Thuật toán kiểm tra số nguyên tố tối ưu hơn được xây dựng dựa trên một nhận xét quan trọng trong toán học: nếu một số n không phải là số nguyên tố, thì chắc chắn nó sẽ có ít nhất một ước số nhỏ hơn hoặc bằng căn bậc hai của n. Nhờ đó, thay vì kiểm tra từ 2 đến n – 1 như cách cơ bản, ta chỉ cần kiểm tra trong khoảng từ 2 đến √n, giúp giảm đáng kể số lần lặp và tăng hiệu suất.

Cách thực hiện:

• • Nếu n < 2 → không phải số nguyên tố
  • Nếu n ≥ 2 → chỉ cần kiểm tra các số từ 2 đến √n
  • Nếu tồn tại số i trong khoảng này mà n chia hết cho i → n không phải số nguyên tố
  • Nếu không có ước số nào → n là số nguyên tố

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

• • √29 ≈ 5.38 → chỉ cần kiểm tra các số từ 2 đến 5
  • Các số 2, 3, 4, 5 đều không chia hết cho 29
  • Kết luận: 29 là số nguyên tố

So với phương pháp cơ bản, thuật toán này giúp giảm độ phức tạp từ O(n) xuống còn O(√n), đặc biệt hiệu quả khi làm việc với các số lớn. Đây cũng là cách tiếp cận phổ biến nhất khi viết chương trình kiểm tra số nguyên tố trong Python.

￭ Xem Thêm: Dấu // Trong Python Là Gì? Tổng Hợp Các Toán Tử Trong Lập Trình Python

Cách kiểm tra số nguyên tố Python từ cơ bản đến nâng cao

Có nhiều phương pháp khác nhau để kiểm tra số nguyên tố Python, mỗi cách sẽ phù hợp với từng nhu cầu và mức độ hiểu biết khác nhau của người học. Dưới đây là các cách phổ biến và hiệu quả giúp bạn triển khai bài toán này một cách dễ dàng và tối ưu hơn:

Cách 1: Dùng vòng lặp for để tìm số nguyên tố Python

Dùng vòng lặp for là phương pháp cơ bản và dễ hiểu nhất để kiểm tra một số có phải là số nguyên tố trong Python hay không. Ý tưởng chính là thử chia số cần kiểm tra cho tất cả các số từ 2 đến n – 1, nếu tồn tại số nào chia hết thì đó không phải là số nguyên tố.

Dưới đây là ví dụ minh họa:

n = int(input(“Nhập số: “)) if n < 2:     print(“Không phải số nguyên tố”) else:     for i in range(2, n):         if n % i == 0:             print(“Không phải số nguyên tố”)             break     else:         print(“Là số nguyên tố”)

Giải thích:

• • Nếu n < 2 → loại ngay vì không phải số nguyên tố
  • Sử dụng vòng lặp for để duyệt từ 2 đến n – 1
  • Nếu tìm thấy i sao cho n % i == 0 → kết luận không phải số nguyên tố và dừng vòng lặp
  • Nếu vòng lặp kết thúc mà không gặp trường hợp chia hết → n là số nguyên tố

Ví dụ:

• • n = 7 → không có số nào từ 2 đến 6 chia hết → là số nguyên tố
  • n = 8 → 8 chia hết cho 2 → không phải số nguyên tố

Ưu điểm của phương pháp này là dễ hiểu, phù hợp với người mới học lập trình. Tuy nhiên, nhược điểm là phải kiểm tra nhiều lần lặp, nên sẽ kém hiệu quả khi xử lý các số lớn.

Cách 2: Tối ưu kiểm tra số nguyên tố Python với căn bậc hai

Phương pháp này cải thiện đáng kể hiệu suất bằng cách tận dụng một tính chất quan trọng: nếu một số n có ước số, thì ít nhất một trong các ước đó sẽ nhỏ hơn hoặc bằng căn bậc hai của n. Vì vậy, thay vì kiểm tra toàn bộ từ 2 đến n – 1, ta chỉ cần duyệt đến √n là đủ để đưa ra kết luận.

Dưới đây là ví dụ minh họa:

import math n = int(input(“Nhập số: “)) if n < 2:     print(“Không phải số nguyên tố”) else:     for i in range(2, int(math.sqrt(n)) + 1):         if n % i == 0:             print(“Không phải số nguyên tố”)             break     else:         print(“Là số nguyên tố”)

Giải thích:

• • Nếu n < 2 → không phải số nguyên tố
  • Tính căn bậc hai của n và chỉ duyệt từ 2 đến giá trị này
  • Nếu tồn tại i mà n chia hết → kết luận không phải số nguyên tố
  • Nếu không tìm thấy ước số nào → n là số nguyên tố

Ví dụ:

• • n = 29 → √29 ≈ 5 → chỉ cần kiểm tra từ 2 đến 5 → không chia hết → là số nguyên tố
  • n = 49 → √49 = 7 → kiểm tra đến 7 → 49 % 7 = 0 → không phải số nguyên tố

So với cách kiểm tra cơ bản, phương pháp này giúp giảm số lần lặp đáng kể, từ đó cải thiện tốc độ xử lý, đặc biệt khi làm việc với các số lớn.

￭ Xem Thêm: Học Python Để Làm Gì? Cơ Hội Việc Làm & Mức Lương Python Developer [2026]

Cách 3: Dùng hàm kiểm tra số nguyên tố Python

Thay vì viết lại logic kiểm tra nhiều lần, bạn có thể đóng gói thuật toán vào một hàm để tái sử dụng linh hoạt trong chương trình. Cách này giúp code gọn gàng hơn, dễ bảo trì và đặc biệt hữu ích khi cần kiểm tra nhiều giá trị khác nhau.

Dưới đây là ví dụ minh họa:

def is_prime(n):     if n < 2:         return False     for i in range(2, int(n**0.5) + 1):         if n % i == 0:             return False     return True # Sử dụng hàm n = int(input(“Nhập số: “)) if is_prime(n):     print(“Là số nguyên tố”) else:     print(“Không phải số nguyên tố”)

Giải thích:

• • Hàm is_prime(n) nhận vào một số nguyên n
  • Trả về False nếu n < 2 hoặc tìm thấy ước số chia hết
  • Trả về True nếu không có ước số nào thỏa điều kiện
  • Áp dụng kiểm tra đến √n để đảm bảo hiệu năng tốt

Ưu điểm của cách này là giúp bạn dễ dàng tái sử dụng trong nhiều bài toán khác nhau, đồng thời làm cho code trở nên rõ ràng hơn nhờ việc tách biệt logic xử lý. Ngoài ra, việc sử dụng hàm cũng giúp bạn thuận tiện hơn khi tích hợp vào các chương trình lớn hoặc những dự án phức tạp. Chính vì vậy, phương pháp này được sử dụng phổ biến trong thực tế nhờ tính linh hoạt và khả năng mở rộng cao.

Cách 4: Sử dụng thuật toán Sieve of Eratosthenes

Thuật toán Sieve of Eratosthenes là một phương pháp hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số n cho trước. Thay vì kiểm tra từng số riêng lẻ, thuật toán này hoạt động bằng cách loại bỏ dần các số không phải nguyên tố, giúp tiết kiệm thời gian khi cần xử lý nhiều giá trị cùng lúc.

Ý tưởng chính:

• • Tạo một danh sách từ 0 đến n và giả sử tất cả đều là số nguyên tố
  • Bắt đầu từ số 2, lần lượt loại bỏ các bội số của nó (vì chắc chắn không phải số nguyên tố)
  • Tiếp tục với các số tiếp theo chưa bị loại bỏ cho đến √n

Dưới đây là ví dụ minh họa:

n = int(input(“Nhập n: “)) is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1):     if is_prime[i]:         for j in range(i * i, n + 1, i):             is_prime[j] = False # In các số nguyên tố for i in range(2, n + 1):     if is_prime[i]:         print(i, end=” “)

Giải thích:

• • Tạo mảng is_prime để đánh dấu số nguyên tố
  • Bắt đầu từ i = 2, nếu i là số nguyên tố thì loại bỏ các bội số của i
  • Bắt đầu loại từ i * i để tối ưu hiệu năng
  • Sau khi hoàn tất, các vị trí còn lại có giá trị True chính là số nguyên tố

Ưu điểm của thuật toán này là rất nhanh khi cần tìm nhiều số nguyên tố trong một khoảng lớn, với độ phức tạp khoảng O(n log log n). Tuy nhiên, nó sẽ tốn thêm bộ nhớ để lưu trữ mảng đánh dấu, nên phù hợp hơn khi làm việc với giới hạn n không quá lớn.

Cách 5: Sử dụng thư viện Sympy kiểm tra số nguyên tố

Một cách nhanh chóng và tiện lợi để kiểm tra số nguyên tố trong Python là sử dụng thư viện Sympy – một thư viện mạnh về toán học. Thay vì tự xây dựng thuật toán, bạn có thể tận dụng sẵn hàm isprime() để kiểm tra một số có phải là số nguyên tố hay không chỉ với một dòng code.

Dưới đây là ví dụ minh họa:

from sympy import isprime n = int(input(“Nhập số: “)) if isprime(n):     print(“Là số nguyên tố”) else:     print(“Không phải số nguyên tố”)

Giải thích:

• • Import hàm isprime từ thư viện Sympy
  • Hàm isprime(n) sẽ trả về True nếu n là số nguyên tố, ngược lại trả về False
  • Bạn không cần quan tâm đến thuật toán phía sau vì thư viện đã xử lý tối ưu sẵn

Ưu điểm của phương pháp này là cực kỳ đơn giản, dễ sử dụng và cho kết quả nhanh chóng, đặc biệt phù hợp khi bạn cần kiểm tra số nguyên tố trong các dự án thực tế. Tuy nhiên, nhược điểm là bạn phải cài đặt thêm thư viện bên ngoài và phụ thuộc vào môi trường chạy chương trình.

￭ Xem Thêm: 20+ Ứng Dụng Của Python Trong Các Lĩnh Vực Thực Tế [Cập Nhật 2026]

Bài tập về số nguyên tố trong Python (Có code mẫu chi tiết)

Sau khi đã nắm vững các phương pháp kiểm tra số nguyên tố Python, việc thực hành qua bài tập sẽ giúp bạn hiểu sâu hơn và áp dụng linh hoạt trong nhiều tình huống khác nhau. Dưới đây là một số bài tập kèm đáp án chi tiết để bạn luyện tập và củng cố kiến thức:

Bài 1: Liệt kê tất cả các số nguyên tố nhỏ hơn n

Bài toán yêu cầu liệt kê tất cả các số nguyên tố nhỏ hơn một số n cho trước. Đây là dạng bài cơ bản giúp bạn luyện tập việc kết hợp vòng lặp và hàm kiểm tra số nguyên tố trong Python.

Yêu cầu: Nhập một số nguyên dương n, in ra tất cả các số nguyên tố nhỏ hơn n.

Cách làm:

• • Duyệt từng số từ 2 đến n – 1
  • Với mỗi số, kiểm tra xem có phải số nguyên tố hay không
  • Nếu đúng, in ra kết quả

Dưới đây là ví dụ minh họa:

def is_prime(n):     if n < 2:         return False     for i in range(2, int(n**0.5) + 1):         if n % i == 0:             return False     return True n = int(input(“Nhập n: “)) for i in range(2, n):     if is_prime(i):         print(i, end=” “)

Giải thích:

• • Sử dụng hàm is_prime() để kiểm tra từng số
  • Vòng lặp for duyệt qua các giá trị nhỏ hơn n
  • Nếu số nào thỏa điều kiện, in ra cùng một dòng

Ví dụ:

• • Nhập n = 10 → Kết quả: 2 3 5 7
  • Nhập n = 20 → Kết quả: 2 3 5 7 11 13 17 19

Bài 2: Tìm số nguyên tố trong khoảng a đến b

Bài toán yêu cầu tìm và liệt kê các số nguyên tố nằm trong một khoảng xác định từ a đến b. Đây là dạng bài giúp bạn rèn luyện khả năng kết hợp điều kiện, vòng lặp và tái sử dụng hàm kiểm tra số nguyên tố đã học.

Yêu cầu: Nhập hai số nguyên a và b (a < b), in ra tất cả các số nguyên tố trong khoảng từ a đến b.

Cách làm:

• • Duyệt qua từng số trong khoảng từ a đến b
  • Với mỗi số, kiểm tra xem có phải là số nguyên tố hay không
  • Nếu đúng, in ra kết quả

Dưới đây là ví dụ minh họa:

def is_prime(n):     if n < 2:         return False     for i in range(2, int(n**0.5) + 1):         if n % i == 0:             return False     return True a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) for i in range(a, b + 1):     if is_prime(i):         print(i, end=” “)

Giải thích:

• • Sử dụng lại hàm is_prime() để kiểm tra từng số
  • Vòng lặp for chạy từ a đến b (bao gồm cả b)
  • Nếu số thỏa điều kiện là số nguyên tố thì in ra

Ví dụ:

• • Nhập a = 5, b = 15 → Kết quả: 5 7 11 13
  • Nhập a = 10, b = 30 → Kết quả: 11 13 17 19 23 29

Bài 3: Kiểm tra số nguyên tố trong mảng Python

Bài toán yêu cầu kiểm tra các phần tử trong một mảng (list) và xác định những số nào là số nguyên tố. Đây là dạng bài giúp bạn kết hợp giữa cấu trúc dữ liệu (mảng) và hàm kiểm tra số nguyên tố trong Python.

Yêu cầu: Nhập một mảng số nguyên, in ra các phần tử là số nguyên tố trong mảng đó.

Cách làm:

• • Duyệt qua từng phần tử trong mảng
  • Với mỗi phần tử, kiểm tra xem có phải số nguyên tố hay không
  • Nếu đúng, in ra kết quả

Dưới đây là ví dụ minh họa:

def is_prime(n):     if n < 2:         return False     for i in range(2, int(n**0.5) + 1):         if n % i == 0:             return False     return True arr = list(map(int, input(“Nhập các phần tử: “).split())) for x in arr:     if is_prime(x):         print(x, end=” “)

Giải thích:

• • Sử dụng hàm is_prime() để kiểm tra từng phần tử trong mảng
  • Dùng vòng lặp for để duyệt qua list arr
  • Nếu phần tử là số nguyên tố thì in ra

Ví dụ:

• • Nhập: 2 4 5 6 7 9 → Kết quả: 2 5 7
  • Nhập: 10 11 12 13 14 → Kết quả: 11 13

Bài 4: Phân tích số nguyên dương n thành thừa số nguyên tố

Bài toán yêu cầu phân tích một số nguyên dương n thành tích các thừa số nguyên tố. Đây là dạng bài quan trọng giúp bạn hiểu sâu hơn về bản chất của số nguyên tố và cách áp dụng trong các thuật toán liên quan đến phân tích số.

Yêu cầu: Nhập một số nguyên dương n, phân tích n thành tích các thừa số nguyên tố.

Cách làm:

• • Bắt đầu từ số nhỏ nhất là 2
  • Trong khi n còn chia hết cho i, liên tục chia và in ra i
  • Sau đó tăng i lên và tiếp tục kiểm tra
  • Lặp lại cho đến khi n = 1

Dưới đây là ví dụ minh họa:

n = int(input(“Nhập n: “)) i = 2 while n > 1:     if n % i == 0:         print(i, end=” “)         n //= i     else:         i += 1

Giải thích:

• • Biến i bắt đầu từ 2 (số nguyên tố nhỏ nhất)
  • Nếu n chia hết cho i → in i và chia n cho i
  • Nếu không chia hết → tăng i lên để kiểm tra tiếp
  • Lặp lại cho đến khi n giảm về 1

Ví dụ:

• • Nhập n = 12 → Kết quả: 2 2 3 (vì 12 = 2 × 2 × 3)
  • Nhập n = 30 → Kết quả: 2 3 5 (vì 30 = 2 × 3 × 5)

Qua bài viết này, bạn đã nắm được nhiều phương pháp khác nhau để kiểm tra số nguyên tố Python, cũng như hiểu rõ cách áp dụng vào từng bài toán cụ thể trong lập trình. Hy vọng những kiến thức và ví dụ minh họa trên sẽ giúp bạn tự tin hơn khi làm việc với các bài toán liên quan đến số nguyên tố và phát triển kỹ năng lập trình Python của mình.

￭ Xem Thêm: TOP 30+ Khóa Học Python TPHCM Chất Lượng & Uy Tín Nhất [UPDATE 2026]