Số nguyên tố và số Palidome với Python

Giới thiệu bài toán

Bài toán yêu cầu tìm tất cả các số vừa là số nguyên tố vừa là số Palindrome (hay còn gọi là số đối xứng). Số Palindrome là số đọc từ trái sang phải hay từ phải sang trái đều giống nhau, ví dụ như 121, 1221, 12321,…

Các bước thực hiện thuật toán

1. Xây dựng hàm kiểm tra số nguyên tố.
2. Xây dựng hàm kiểm tra số Palindrome.
3. Duyệt tất cả các số nguyên dương từ 1 đến giá trị cho trước.
4. Kiểm tra từng số này: a. Nếu là số nguyên tố và số Palindrome thì thêm vào danh sách kết quả.
5. Trả về danh sách kết quả.

Cài đặt thuật toán với Python

#Xây dựng hàm kiểm tra số nguyên tố:
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

#Xây dựng hàm kiểm tra số Palindrome:
def is_palindrome(n):
    return str(n) == str(n)[::-1]

#Duyệt tất cả các số nguyên dương từ 1 đến n
def find_prime_palindromes(n):
    result = []
    for i in range(1, n+1):
        if is_prime(i) and is_palindrome(i):
            result.append(i)
    return result

#Kiểm tra từng số này và in ra kết quả:
print(find_prime_palindromes(100))
# Output: [2, 3, 5, 7, 11, 101]

Đánh giá độ phức tạp

• Hàm kiểm tra số nguyên tố có độ phức tạp O(sqrt(n)).
• Hàm kiểm tra số Palindrome có độ phức tạp O(log(n)).
• Duyệt tất cả các số nguyên dương từ 1 đến n có độ phức tạp O(n).
• Vậy độ phức tạp của thuật toán là O(n*sqrt(n)*log(n)).

Tối ưu bài toán

Để tối ưu thuật toán tìm tất cả các số vừa là số nguyên tố vừa là số Palindrome, ta có thể áp dụng phương pháp sàng nguyên tố Eratosthenes để loại bỏ các số không phải số nguyên tố và giảm thiểu độ phức tạp của thuật toán.

Các bước thực hiện thuật toán tối ưu

1. Xây dựng hàm kiểm tra số Palindrome.
2. Sàng nguyên tố Eratosthenes để loại bỏ các số không phải số nguyên tố: a. Khởi tạo một mảng chứa True cho tất cả các phần tử từ 2 đến n. b. Duyệt từng phần tử trong mảng và đánh dấu các bội số của nó là False.
3. Duyệt tất cả các số nguyên dương từ 2 đến n: a. Nếu là số Palindrome và giá trị tương ứng trong mảng sàng nguyên tố là True, thì thêm vào danh sách kết quả.
4. Trả về danh sách kết quả.

Cài đặt thuật toán với Python

#Xây dựng hàm kiểm tra số Palindrome:
def is_palindrome(n):
    return str(n) == str(n)[::-1] 

#Sàng nguyên tố Eratosthenes:
def eratosthenes(n):
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i**2, n+1, i):
                sieve[j] = False
    return sieve

#Duyệt tất cả các số nguyên dương từ 2 đến 100:
def find_prime_palindromes(n):
    result = []
    sieve = eratosthenes(n)
    for i in range(2, n+1):
        if sieve[i] and is_palindrome(i):
            result.append(i)
    return result

#Kiểm tra từng số và in ra kết quả:
print(find_prime_palindromes(100))
# Output: [2, 3, 5, 7, 11, 101]

Đánh giá độ phức tạp

Độ phức tạp của thuật toán tìm tất cả các số vừa là số nguyên tố vừa là số Palindrome là O(n√n), trong đó n là giới hạn trên của khoảng các số cần tìm kiếm.

Giải thích:

• Hàm kiểm tra số Palindrome có độ phức tạp O(log(n)).
• Sàng nguyên tố Eratosthenes được sử dụng để loại bỏ các số không phải số nguyên tố. Độ phức tạp của sàng nguyên tố Eratosthenes là O(n log log n). Tuy nhiên, trong trường hợp này, chúng ta chỉ cần sàng nguyên tố cho các số từ 2 đến n, do đó, độ phức tạp sẽ là O(n log log n).
• Duyệt tất cả các số nguyên dương từ 2 đến n có độ phức tạp O(n).
• Vậy, độ phức tạp của thuật toán là O(n√n).

Tuy nhiên, khi giới hạn trên n tăng lên, độ phức tạp sẽ tăng theo một cách không đáng kể. Do đó, thuật toán này là tương đối hiệu quả và có thể được sử dụng trong nhiều trường hợp thực tế.