Bài 2.20. Thực hành Python - Sinh số nguyên tố
Bài 2.20. Thực hành Python: sinh số nguyên tố
Chào mừng các bạn đến với bài thực hành Python tiếp theo! Hôm nay, chúng ta sẽ đào sâu vào một chủ đề toán học kinh điển nhưng luôn thú vị trong lập trình: số nguyên tố. Chúng không chỉ là nền tảng của nhiều thuật toán mã hóa mà còn là một bài toán tuyệt vời để rèn luyện tư duy logic và kỹ năng lập trình Python.
Trong bài này, chúng ta sẽ tìm hiểu:
- Số nguyên tố là gì?
- Cách viết hàm Python để kiểm tra một số có phải là số nguyên tố hay không (với các mức độ tối ưu khác nhau).
- Cách sinh ra một danh sách các số nguyên tố nhỏ hơn một giới hạn cho trước.
- Giới thiệu về thuật toán Sàng Eratosthenes - một phương pháp hiệu quả để tìm nhiều số nguyên tố cùng lúc.
Nào, hãy cùng bắt đầu hành trình khám phá những con số đặc biệt này nhé!
1. Số Nguyên Tố Là Gì? - Ôn Lại Khái Niệm Cơ Bản
Trước khi bắt tay vào code, hãy cùng nhắc lại định nghĩa về số nguyên tố.
Một 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 phân biệt là 1 và chính nó.
- Ví dụ về số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19,...
- Số 7 là số nguyên tố vì nó chỉ chia hết cho 1 và 7.
- Số 2 là số nguyên tố duy nhất là số chẵn.
- Ví dụ về số không phải nguyên tố (gọi là hợp số): 4 (chia hết cho 1, 2, 4), 6 (chia hết cho 1, 2, 3, 6), 9 (chia hết cho 1, 3, 9).
- Lưu ý: Số 1 không phải là số nguyên tố vì nó chỉ có một ước số dương là 1. Số 0 cũng không phải là số nguyên tố.
Hiểu rõ định nghĩa này là chìa khóa để xây dựng thuật toán kiểm tra số nguyên tố.
2. Xây Dựng Hàm Kiểm Tra Số Nguyên Tố (isPrime)
Mục tiêu của chúng ta là viết một hàm Python is_prime(n) nhận vào một số nguyên n và trả về True nếu n là số nguyên tố, ngược lại trả về False.
2.1. Phương pháp "Ngây Thơ" (Naive Approach)
Cách đơn giản nhất xuất phát trực tiếp từ định nghĩa: ta kiểm tra xem n có chia hết cho bất kỳ số nào từ 2 đến n-1 hay không. Nếu tìm thấy một số như vậy, n không phải là số nguyên tố.
import math # Sẽ cần dùng thư viện math cho các phần sau
def is_prime_naive(n):
"""
Kiểm tra xem số nguyên n có phải là số nguyên tố hay không (cách cơ bản).
Args:
n: Số nguyên cần kiểm tra.
Returns:
True nếu n là số nguyên tố, False nếu không phải.
"""
# Bước 1: Xử lý các trường hợp cơ bản
if n <= 1:
return False # Số nguyên tố phải lớn hơn 1
# Bước 2: Duyệt qua các số từ 2 đến n-1
# range(2, n) sẽ tạo ra dãy số 2, 3, ..., n-1
for i in range(2, n):
# Bước 3: Kiểm tra tính chia hết
if n % i == 0:
# Nếu n chia hết cho i (với i khác 1 và n), n không phải số nguyên tố
return False
# Bước 4: Nếu vòng lặp kết thúc mà không tìm thấy ước nào
# thì n là số nguyên tố
return True
# --- Ví dụ sử dụng ---
print(f"Kiểm tra số 7 (naive): {is_prime_naive(7)}")
print(f"Kiểm tra số 10 (naive): {is_prime_naive(10)}")
print(f"Kiểm tra số 1 (naive): {is_prime_naive(1)}")
print(f"Kiểm tra số 2 (naive): {is_prime_naive(2)}")
Giải thích code:
if n <= 1:: Đầu tiên, ta loại bỏ ngay các trường hợpnnhỏ hơn hoặc bằng 1, vì theo định nghĩa chúng không phải số nguyên tố.for i in range(2, n):: Ta dùng vòng lặpforđể duyệt qua tất cả các sốicó thể là ước củan, bắt đầu từ 2 và kết thúc ởn-1.if n % i == 0:: Bên trong vòng lặp, ta dùng phép toán chia lấy dư (%). Nếun % ibằng 0, nghĩa lànchia hết choi. Vìinằm trong khoảng(1, n), nênncó nhiều hơn 2 ước số. Do đó,nkhông phải là số nguyên tố, và ta trả vềFalsengay lập tức.return True: Nếu vòng lặpforchạy hết mà không tìm thấy bất kỳ ước sốinào (tức là không có lệnhreturn Falsenào được thực thi), điều đó có nghĩa lànchỉ chia hết cho 1 và chính nó. Vậynlà số nguyên tố, và hàm trả vềTrue.
Phương pháp này hoạt động đúng, nhưng liệu có cách nào hiệu quả hơn không? Đặc biệt là khi n rất lớn, việc kiểm tra đến n-1 sẽ tốn rất nhiều thời gian.
2.2. Tối Ưu Hóa Lần 1: Chỉ Kiểm Tra Đến Căn Bậc Hai Của n
Chúng ta có thể cải thiện đáng kể hiệu suất bằng một nhận xét toán học quan trọng:
Nếu một số
ncó một ước sốdlớn hơn căn bậc hai củan(d > sqrt(n)), thì nó cũng phải có một ước sốknhỏ hơn hoặc bằng căn bậc hai củan(k <= sqrt(n)) sao chon = d * k.
Điều này có nghĩa là: Nếu n không có ước số nào từ 2 đến sqrt(n), thì nó chắc chắn không có ước số nào từ sqrt(n) đến n-1 (ngoại trừ chính n nếu n là nguyên tố).
Vì vậy, chúng ta chỉ cần kiểm tra các ước số tiềm năng i trong khoảng từ 2 đến floor(sqrt(n)) (phần nguyên của căn bậc hai của n).
import math
def is_prime_sqrt(n):
"""
Kiểm tra số nguyên tố bằng cách duyệt đến căn bậc hai của n.
Args:
n: Số nguyên cần kiểm tra.
Returns:
True nếu n là số nguyên tố, False nếu không phải.
"""
if n <= 1:
return False
if n == 2:
return True # 2 là số nguyên tố đặc biệt
if n % 2 == 0:
return False # Loại bỏ các số chẵn > 2
# Chỉ cần kiểm tra các ước số lẻ từ 3 đến sqrt(n)
# math.isqrt(n) tính căn bậc hai số nguyên (hiệu quả hơn int(math.sqrt(n)))
# hoặc dùng int(n**0.5) + 1 trong range
limit = math.isqrt(n)
# limit = int(n**0.5) # Cách khác
# Duyệt qua các số lẻ từ 3
# range(start, stop, step)
for i in range(3, limit + 1, 2): # Chỉ kiểm tra số lẻ
if n % i == 0:
return False
return True
# --- Ví dụ sử dụng ---
print(f"\nKiểm tra số 97 (sqrt): {is_prime_sqrt(97)}")
print(f"Kiểm tra số 100 (sqrt): {is_prime_sqrt(100)}")
print(f"Kiểm tra số 2 (sqrt): {is_prime_sqrt(2)}")
# Thử với số lớn hơn
large_prime = 10**9 + 7 # Một số nguyên tố thường dùng trong lập trình thi đấu
print(f"Kiểm tra số {large_prime} (sqrt): {is_prime_sqrt(large_prime)}")
# So sánh với cách naive (sẽ rất chậm nếu chạy)
# print(f"Kiểm tra số {large_prime} (naive): {is_prime_naive(large_prime)}") # Đừng chạy cái này!
Giải thích tối ưu hóa:
if n == 2:: Thêm trường hợp đặc biệt cho số 2.if n % 2 == 0:: Nếunlớn hơn 2 và là số chẵn, nó chắc chắn không phải số nguyên tố. Việc kiểm tra này giúp loại bỏ một nửa số trường hợp ngay lập tức.limit = math.isqrt(n): Tính giới hạn trên cho vòng lặp là căn bậc hai củan. Hàmmath.isqrt(n)(từ Python 3.8) trả về phần nguyên của căn bậc hai, rất tiện lợi. Nếu dùng phiên bản Python cũ hơn, có thể dùnglimit = int(math.sqrt(n))hoặclimit = int(n**0.5).for i in range(3, limit + 1, 2):: Vòng lặp bây giờ:- Bắt đầu từ 3 (vì đã xử lý số 2 và các số chẵn khác).
- Kết thúc tại
limit(phải cộng 1 vìrangekhông bao gồm điểm cuối). - Bước nhảy là 2 (
step=2), nghĩa là chỉ kiểm tra các số lẻ: 3, 5, 7,... Điều này lại giảm đi một nửa số lần kiểm tra nữa!
Sự khác biệt về tốc độ giữa is_prime_naive và is_prime_sqrt là rất lớn, đặc biệt với các số lớn!
3. Sinh Danh Sách Các Số Nguyên Tố Nhỏ Hơn N
Bây giờ chúng ta đã có hàm is_prime hiệu quả, làm thế nào để tạo ra một danh sách chứa tất cả các số nguyên tố từ 2 đến một giới hạn N cho trước? Rất đơn giản: duyệt qua tất cả các số từ 2 đến N và sử dụng hàm is_prime để kiểm tra từng số.
def generate_primes_upto_n(N):
"""
Sinh ra danh sách các số nguyên tố từ 2 đến N.
Args:
N: Giới hạn trên (bao gồm cả N nếu N là nguyên tố).
Returns:
Một list chứa các số nguyên tố <= N.
"""
primes = [] # Khởi tạo danh sách rỗng
for num in range(2, N + 1): # Duyệt từ 2 đến N
if is_prime_sqrt(num): # Sử dụng hàm kiểm tra đã tối ưu
primes.append(num) # Thêm số nguyên tố vào danh sách
return primes
# --- Ví dụ sử dụng ---
limit = 30
prime_list = generate_primes_upto_n(limit)
print(f"\nCác số nguyên tố nhỏ hơn hoặc bằng {limit}:")
print(prime_list)
limit_large = 100
prime_list_large = generate_primes_upto_n(limit_large)
print(f"\nCác số nguyên tố nhỏ hơn hoặc bằng {limit_large}:")
print(prime_list_large)
# Cách viết ngắn gọn hơn dùng List Comprehension (nếu bạn đã quen)
def generate_primes_upto_n_comprehension(N):
return [num for num in range(2, N + 1) if is_prime_sqrt(num)]
print(f"\nCác số nguyên tố <= 100 (comprehension):")
print(generate_primes_upto_n_comprehension(100))
Giải thích code:
primes = []: Tạo một danh sách rỗng để chứa kết quả.for num in range(2, N + 1):: Lặp qua từng sốnumtừ 2 đếnN(nhớ cộng 1 chorange).if is_prime_sqrt(num):: Gọi hàmis_prime_sqrt(phiên bản tối ưu) để kiểm tra xemnumhiện tại có phải là số nguyên tố không.primes.append(num): Nếuis_prime_sqrttrả vềTrue, thêmnumvào danh sáchprimes.return primes: Sau khi kiểm tra hết các số, trả về danh sách các số nguyên tố đã tìm được.
Phiên bản dùng list comprehension [num for num in range(2, N + 1) if is_prime_sqrt(num)] thực hiện chính xác logic tương tự nhưng trong một dòng code duy nhất, trông gọn gàng hơn.
Phương pháp này hoạt động tốt cho các giá trị N không quá lớn. Tuy nhiên, nếu bạn cần tìm tất cả các số nguyên tố đến một N rất lớn (ví dụ: hàng triệu), việc gọi is_prime lặp đi lặp lại cho từng số vẫn chưa phải là cách tối ưu nhất.
4. Giới Thiệu Sàng Eratosthenes (Sieve of Eratosthenes) - Phương Pháp Hiệu Quả Hơn
Khi cần tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng N, có một thuật toán cổ điển và hiệu quả hơn nhiều so với việc kiểm tra từng số: Sàng Eratosthenes.
Ý tưởng cốt lõi:
- Tạo một danh sách (hoặc mảng boolean) đánh dấu tất cả các số từ 2 đến
Nlà "có khả năng là số nguyên tố" (ví dụ: đánh dấu làTrue). - Bắt đầu từ số nguyên tố đầu tiên là
p = 2. - Đánh dấu tất cả các bội số của
p(là2*p,3*p,4*p, ...) cho đếnNlà "không phải số nguyên tố" (ví dụ: đánh dấu làFalse). - Tìm số tiếp theo trong danh sách lớn hơn
pmà vẫn còn được đánh dấu là "có khả năng là số nguyên tố". Số này chính là số nguyên tố tiếp theo. Gánpbằng số này. - Lặp lại bước 3 và 4 cho đến khi
p*pvượt quáN. Tại sao chỉ cần đến `pp > N?* Bởi vì nếu một sốk < Nlà hợp số, nó phải có một ước nguyên tốqsao choq*q <= k < N. Tất cả các bội củaqđã được sàng lọc khi thuật toán xử lý đếnq`. - Cuối cùng, tất cả các số còn lại được đánh dấu là "có khả năng là số nguyên tố" chính là các số nguyên tố cần tìm.
Hãy xem cách triển khai bằng Python:
def sieve_of_eratosthenes(N):
"""
Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng N bằng Sàng Eratosthenes.
Args:
N: Giới hạn trên.
Returns:
Một list chứa các số nguyên tố <= N.
"""
if N < 2:
return []
# Bước 1: Tạo list boolean, ban đầu giả định tất cả đều là nguyên tố
# is_prime[i] = True nghĩa là số i có thể là nguyên tố
# Kích thước N+1 để chỉ số list tương ứng với số (từ 0 đến N)
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False # 0 và 1 không phải nguyên tố
# Bước 2 & 4: Lặp qua các số từ 2 đến sqrt(N)
p = 2
while (p * p <= N):
# Nếu is_prime[p] vẫn là True, thì p là số nguyên tố
if is_prime[p] == True:
# Bước 3: Đánh dấu tất cả bội của p là không phải nguyên tố
# Bắt đầu từ p*p, vì các bội nhỏ hơn (như 2*p, 3*p nếu p > 2)
# đã được đánh dấu bởi các số nguyên tố nhỏ hơn p rồi.
# Ví dụ: 6 đã bị đánh dấu bởi 2, 9 sẽ bị đánh dấu bởi 3,...
for i in range(p * p, N + 1, p):
is_prime[i] = False
p += 1 # Chuyển sang số tiếp theo để kiểm tra
# Bước 6: Thu thập kết quả
primes = []
for p in range(2, N + 1):
if is_prime[p]:
primes.append(p)
return primes
# --- Ví dụ sử dụng ---
limit_sieve = 100
prime_list_sieve = sieve_of_eratosthenes(limit_sieve)
print(f"\nCác số nguyên tố <= {limit_sieve} (Sieve of Eratosthenes):")
print(prime_list_sieve)
limit_sieve_large = 1000
print(f"\nĐang tìm các số nguyên tố <= {limit_sieve_large} bằng Sieve...")
prime_list_sieve_large = sieve_of_eratosthenes(limit_sieve_large)
print(f"Tìm thấy {len(prime_list_sieve_large)} số nguyên tố.")
# print(prime_list_sieve_large) # Có thể in ra nếu muốn xem
Giải thích code Sàng Eratosthenes:
is_prime = [True] * (N + 1): Tạo một list boolean dàiN+1phần tử.is_prime[i]sẽ cho biết sốicó được coi là nguyên tố hay không (tại thời điểm hiện tại). Ban đầu, tất cả đều làTrue(trừ 0 và 1).is_prime[0] = is_prime[1] = False: Đánh dấu 0 và 1 không phải nguyên tố.p = 2: Bắt đầu với số nguyên tố đầu tiên.while (p * p <= N):: Vòng lặp chính chỉ chạy đến khip*pvượt quáNnhư đã giải thích ở trên.if is_prime[p] == True:: Nếupchưa bị đánh dấu làFalsebởi một số nguyên tố nhỏ hơn, thìpchính là một số nguyên tố.for i in range(p * p, N + 1, p): is_prime[i] = False: Đây là bước "sàng". Ta duyệt qua tất cả các bội củap, bắt đầu từp*p(tối ưu hóa quan trọng!) và đánh dấu chúng làFalse(không phải nguyên tố). Bước nhảy làp.p += 1: Chuyển sang số tiếp theo để kiểm tra.primes = []; for p in range(2, N + 1): if is_prime[p]: primes.append(p): Sau khi quá trình sàng lọc kết thúc, duyệt lại listis_primetừ 2 đếnN. Nếuis_prime[p]vẫn làTrue, thìplà số nguyên tố, ta thêm nó vào list kết quảprimes.
Thuật toán Sàng Eratosthenes cực kỳ hiệu quả khi bạn cần tìm tất cả các số nguyên tố trong một khoảng lớn. Độ phức tạp thời gian của nó xấp xỉ O(N log log N), nhanh hơn đáng kể so với O(N * sqrt(N)) của phương pháp gọi is_prime lặp đi lặp lại.
Qua bài thực hành này, bạn không chỉ học được cách kiểm tra và sinh số nguyên tố bằng Python mà còn thấy được tầm quan trọng của việc lựa chọn thuật toán phù hợp và áp dụng các kỹ thuật tối ưu hóa. Số nguyên tố là một cánh cửa dẫn đến nhiều khái niệm thú vị khác trong toán học và khoa học máy tính. Hãy tiếp tục khám phá và thử nghiệm với những con số đặc biệt này nhé!
Khóa học liên quan
Giảm giá!
Comments