32 Học Python - In các số nguyên tố từ m đến n mới nhất

Rate this post

DANH SÁCH TÓM TẮT:

1 Bài 32 : In Các Số Nguyên Tố Từ m Đến n Bằng Python
2 Viết Chương Trình Python
3 Giải Thích Chương Trình các số nguyên tố

Bài 32 : In Các Số Nguyên Tố Từ m Đến n Bằng Python

Giới Thiệu

Bài toán in ra các số nguyên tố trong một khoảng [m, n] là một bài toán phổ biến trong lập trình. Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Bài viết này sẽ hướng dẫn cách giải quyết bài toán này bằng Python một cách hiệu quả.

Ưu Đãi lớn thêm danh sách 10 bài tập python rèn luyện kỹ năng và nâng cao tay nghề:

Cách Xác Định Số Nguyên Tố

Một số x là số nguyên tố nếu:

x > 1.
Không tồn tại số d nào (2 ≤ d ≤ sqrt(x)) mà x % d == 0.

Viết Chương Trình Python

Dưới đây là chương trình Python để in các số nguyên tố trong đoạn [m, n].

import math
# Hàm kiểm tra số nguyên tố
def la_so_nguyen_to(x):
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True
# Hàm in các số nguyên tố trong đoạn [m, n]
def in_so_nguyen_to(m, n):
    primes = [i for i in range(m, n + 1) if la_so_nguyen_to(i)]
    return primes
# Nhập giá trị m và n từ người dùng
m = int(input("Nhập số nguyên m: "))
n = int(input("Nhập số nguyên n: "))
# Kiểm tra điều kiện m phải nhỏ hơn hoặc bằng n
if m > n:
    print("Giá trị m phải nhỏ hơn hoặc bằng n.")
else:
    primes = in_so_nguyen_to(m, n)
    print(f"Các số nguyên tố từ {m} đến {n} là: {primes}")

Giải Thích Chương Trình các số nguyên tố

Hàm la_so_nguyen_to(x): Kiểm tra số x có phải số nguyên tố không bằng cách kiểm tra ước số từ 2 đến sqrt(x).
Hàm in_so_nguyen_to(m, n): Duyệt qua từng số từ m đến n, lọc ra các số nguyên tố.
Nhập giá trị m và n: Nhận hai số nguyên từ người dùng.
Kiểm tra điều kiện m ≤ n: Đảm bảo khoảng hợp lệ trước khi tính toán.
Hiển thị kết quả: Xuất danh sách các số nguyên tố tìm được.

Cách Tối Ưu Bằng Sàng Eratosthenes

Một cách tối ưu hơn là sử dụng thuật toán Sàng Eratosthenes để tìm tất cả số nguyên tố trong khoảng [m, n] nhanh hơn.

# Hàm sử dụng Sàng Eratosthenes để tìm số nguyên tố
def sang_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return is_prime
# Hàm in số nguyên tố từ m đến n
def in_so_nguyen_to_sang(m, n):
    primes = sang_eratosthenes(n)
    return [i for i in range(m, n + 1) if primes[i]]
# Nhập giá trị m và n từ người dùng
m = int(input("Nhập số nguyên m: "))
n = int(input("Nhập số nguyên n: "))
# Kiểm tra điều kiện
if m > n:
    print("Giá trị m phải nhỏ hơn hoặc bằng n.")
else:
    primes = in_so_nguyen_to_sang(m, n)
    print(f"Các số nguyên tố từ {m} đến {n} là: {primes}")

Giải Thích Cách Tối Ưu

Sàng Eratosthenes: Tạo một danh sách đánh dấu các số nguyên tố, sau đó chỉ cần lọc ra các số nguyên tố trong đoạn [m, n].
Độ phức tạp O(n log log n): Nhanh hơn so với kiểm tra từng số riêng lẻ (O(n√n)).

Ứng Dụng

Xác định nhanh các số nguyên tố trong một khoảng.
Tối ưu hóa thuật toán kiểm tra số nguyên tố.
Ứng dụng trong mật mã, thống kê và phân tích dữ liệu.

Kết Luận

Bài toán in các số nguyên tố từ m đến n có thể giải quyết bằng nhiều cách. Cách kiểm tra từng số dễ hiểu nhưng chậm, trong khi Sàng Eratosthenes giúp tối ưu hiệu suất đáng kể. Hy vọng bài viết này giúp bạn hiểu rõ hơn về cách triển khai thuật toán này trong Python!