Chào các em, hôm nay chúng ta sẽ cùng nhau giải một bài tập rất thú vị trong chương trình Tin học lớp 11, liên quan đến việc tìm và đếm các số nguyên tố. Bài tập này không chỉ giúp chúng ta củng cố kiến thức về lập trình mà còn rèn luyện tư duy logic, đặc biệt là cách áp dụng kiến thức toán học vào giải quyết vấn đề.

Chúng ta sẽ thực hiện bài tập này bằng ngôn ngữ Python, một ngôn ngữ lập trình mạnh mẽ và dễ học.

Bước 1: Hiểu rõ khái niệm số nguyên tố

Trước khi bắt tay vào viết code, chúng ta cần nhắc lại định nghĩa về số nguyên tố.
Một số tự nhiên lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai ước số dương phân biệt là 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11 là các số nguyên tố.
Số 1 không phải là số nguyên tố vì nó chỉ có một ước là 1.
Số 4 không phải là số nguyên tố vì nó có ba ước là 1, 2, và 4.

Bước 2: Xây dựng thuật toán kiểm tra một số có phải là số nguyên tố hay không

Để giải bài toán này, việc đầu tiên chúng ta cần làm là có một “công cụ” để kiểm tra xem một số bất kỳ có phải là số nguyên tố hay không.

Giả sử chúng ta có một số tự nhiên \(n\). Làm thế nào để kiểm tra \(n\) có phải là số nguyên tố?
– Nếu \(n\) nhỏ hơn 2, chắc chắn \(n\) không phải là số nguyên tố.
– Nếu \(n\) bằng 2, thì \(n\) là số nguyên tố (trường hợp đặc biệt).
– Nếu \(n\) lớn hơn 2, chúng ta sẽ kiểm tra xem \(n\) có chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của \(n\) hay không.
– Tại sao lại là căn bậc hai của \(n\)? Bởi vì nếu \(n\) có một ước số \(d\) lớn hơn \(\sqrt{n}\), thì \(n\) cũng sẽ có một ước số \(n/d\) nhỏ hơn \(\sqrt{n}\). Do đó, chúng ta chỉ cần kiểm tra các ước số từ 2 đến \(\sqrt{n}\).
– 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ố.
– Nếu \(n\) không chia hết cho bất kỳ số nào trong khoảng này, thì \(n\) là số nguyên tố.

Chúng ta sẽ đóng gói logic này vào một hàm (function) trong Python để dễ dàng tái sử dụng.

python
import math

def is_prime(num):
if num < 2: return False if num == 2: return True if num % 2 == 0: # Loại bỏ các số chẵn lớn hơn 2 ngay lập tức return False # Kiểm tra các ước số lẻ từ 3 đến căn bậc hai của num # Ta chỉ cần kiểm tra các số lẻ vì các số chẵn đã được loại bỏ ở trên. # Vòng lặp tăng 2 để chỉ duyệt qua các số lẻ. for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True Giải thích chi tiết hàm \(is_prime(num)\): - \(import math\): Dòng này nhập thư viện \(math\) để chúng ta có thể sử dụng hàm tính căn bậc hai \(math.sqrt()\). - \(def is_prime(num):\): Định nghĩa một hàm tên là \(is_prime\) nhận vào một tham số là \(num\) (số cần kiểm tra). - \(if num < 2:\): Nếu \(num\) nhỏ hơn 2 (tức là 0, 1, hoặc các số âm), nó không phải số nguyên tố. Trả về \(False\). - \(if num == 2:\): Nếu \(num\) bằng 2, nó là số nguyên tố. Trả về \(True\). - \(if num % 2 == 0:\): Nếu \(num\) chia hết cho 2 (và \(num\) lớn hơn 2 vì đã qua kiểm tra \(num == 2\)), thì \(num\) là số chẵn lớn hơn 2, do đó không phải số nguyên tố. Trả về \(False\). - \(for i in range(3, int(math.sqrt(num)) + 1, 2):\): Đây là vòng lặp chính. - \(range(start, stop, step)\): Hàm \(range\) tạo ra một dãy số. - \(3\): Bắt đầu kiểm tra từ số 3. - \(int(math.sqrt(num)) + 1\): Kết thúc kiểm tra tại phần nguyên của căn bậc hai của \(num\) cộng thêm 1. Chúng ta cộng 1 để đảm bảo rằng nếu căn bậc hai là một số nguyên, chúng ta vẫn kiểm tra nó. - \(2\): Bước nhảy của vòng lặp là 2. Điều này có nghĩa là chúng ta chỉ kiểm tra các số lẻ (3, 5, 7, ...). Điều này là tối ưu vì chúng ta đã loại bỏ hết các số chẵn ở bước trước. - \(if num % i == 0:\): Bên trong vòng lặp, nếu \(num\) chia hết cho \(i\) (tức là tìm thấy một ước khác 1 và chính nó), thì \(num\) không phải là số nguyên tố. Trả về \(False\). - \(return True\): Nếu vòng lặp kết thúc mà không tìm thấy ước nào, nghĩa là \(num\) chỉ chia hết cho 1 và chính nó, do đó nó là số nguyên tố. Trả về \(True\). Bước 3: Lặp qua các số từ 1 đến 1000 và sử dụng hàm \(is_prime\)

Bây giờ, chúng ta sẽ viết phần code chính để thực hiện yêu cầu của đề bài: in ra tất cả các số nguyên tố từ 1 đến 1000 và đếm chúng.

Chúng ta cần một biến để đếm số lượng số nguyên tố, và một vòng lặp để duyệt qua từng số từ 1 đến 1000.

python
prime_count = 0 # Khởi tạo biến đếm số lượng số nguyên tố
prime_numbers = [] # Tạo một danh sách để lưu trữ các số nguyên tố tìm được

print(“Các số nguyên tố từ 1 đến 1000 là:”)

# Vòng lặp duyệt qua các số từ 1 đến 1000 (bao gồm cả 1000)
for number in range(1, 1001):
if is_prime(number): # Gọi hàm is_prime để kiểm tra
print(number, end=” “) # In số nguyên tố và thêm khoảng trắng, không xuống dòng mới
prime_count += 1 # Tăng biến đếm lên 1
prime_numbers.append(number) # Thêm số nguyên tố vào danh sách

print(“\n\nTổng số lượng số nguyên tố từ 1 đến 1000 là:”, prime_count)

Giải thích chi tiết phần code này:
– \(prime_count = 0\): Chúng ta khởi tạo một biến \(prime_count\) bằng 0. Biến này sẽ lưu giữ tổng số lượng số nguyên tố mà chúng ta tìm thấy.
– \(prime_numbers = []\): Chúng ta tạo một danh sách rỗng \(prime_numbers\) để có thể lưu lại tất cả các số nguyên tố tìm được, phòng trường hợp sau này chúng ta cần sử dụng lại danh sách này.
– \(print(“Các số nguyên tố từ 1 đến 1000 là:”)\): Dòng này chỉ để thông báo cho người dùng biết chương trình sắp in ra những gì.
– \(for number in range(1, 1001):\): Đây là vòng lặp chính.
– \(range(1, 1001)\): Tạo ra một dãy số bắt đầu từ 1 và kết thúc trước 1001, nghĩa là các số từ 1 đến 1000. Biến \(number\) sẽ lần lượt nhận các giá trị này.
– \(if is_prime(number):\): Với mỗi \(number\) trong vòng lặp, chúng ta gọi hàm \(is_prime\) để kiểm tra xem nó có phải là số nguyên tố hay không. Nếu \(is_prime(number)\) trả về \(True\) (nghĩa là \(number\) là số nguyên tố):
– \(print(number, end=” “)\): Chúng ta in \(number\) ra màn hình. Tham số \(end=” “\) được thêm vào để sau khi in \(number\), chương trình sẽ in ra một khoảng trắng thay vì xuống dòng mới. Điều này giúp các số nguyên tố được in trên cùng một dòng, cách nhau bởi dấu cách.
– \(prime_count += 1\): Chúng ta tăng giá trị của \(prime_count\) lên 1.
– \(prime_numbers.append(number)\): Chúng ta thêm \(number\) vào danh sách \(prime_numbers\).
– \(print(“\n\nTổng số lượng số nguyên tố từ 1 đến 1000 là:”, prime_count)\): Sau khi vòng lặp kết thúc, chúng ta in ra tổng số lượng số nguyên tố. \(\n\n\) được sử dụng để tạo ra hai dòng trống trước khi in kết quả cuối cùng, giúp kết quả hiển thị gọn gàng hơn.

Bước 4: Kết hợp toàn bộ code và chạy thử

Bây giờ, chúng ta sẽ ghép hai phần code lại với nhau để tạo thành một chương trình hoàn chỉnh.

python
import math

# Hàm kiểm tra một số có phải là số nguyên tố hay không
def is_prime(num):
if num < 2: return False if num == 2: return True if num % 2 == 0: return False for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True # Phần chính của chương trình prime_count = 0 prime_numbers = [] print("Các số nguyên tố từ 1 đến 1000 là:") for number in range(1, 1001): if is_prime(number): print(number, end=" ") prime_count += 1 prime_numbers.append(number) print("\n\nTổng số lượng số nguyên tố từ 1 đến 1000 là:", prime_count) Khi chạy đoạn code này, chúng ta sẽ thấy: - Đầu tiên là danh sách các số nguyên tố từ 1 đến 1000, được in ra trên cùng một dòng, cách nhau bởi dấu cách. - Cuối cùng là dòng thông báo tổng số lượng số nguyên tố tìm được. Ví dụ kết quả đầu ra sẽ bắt đầu như sau: Các số nguyên tố từ 1 đến 1000 là: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ... Và kết thúc bằng: ... 991 997 Tổng số lượng số nguyên tố từ 1 đến 1000 là: 168 Lưu ý quan trọng:
– Số 1 không phải là số nguyên tố. Thuật toán của chúng ta đã xử lý đúng trường hợp này với điều kiện \(if num < 2: return False\). - Các số nguyên tố được xác định dựa trên định nghĩa toán học và thuật toán kiểm tra đã được tối ưu hóa. Đây là một bài tập rất cơ bản nhưng lại mang nhiều ý nghĩa, giúp chúng ta hiểu cách phân tích bài toán, xây dựng thuật toán và hiện thực hóa bằng ngôn ngữ lập trình. Các em về nhà thực hành thêm với các khoảng số khác nhau để làm quen nhé! Chúc các em học tốt!