Kiểm tra số Emirp trong Python

Số Emirp (prime viết ngược) là số nguyên tố mà khi đảo ngược chữ số lại được một số nguyên tố khác.

Ví dụ: 97 → đảo ngược 79 (cũng là nguyên tố) → True.

Thuật toán

1. Kiểm tra n có phải nguyên tố không. Nếu không → False.
2. Đảo ngược chữ số của n thành reverse_num.
3. Kiểm tra reverse_num có phải nguyên tố không. Trả về kết quả.

Triển khai

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):  # tối ưu: chỉ duyệt đến căn bậc hai
        if num % i == 0:
            return False
    return True

def solve(num):
    if not is_prime(num):
        return False
    reverse_num = 0
    temp = num
    while temp != 0:
        d = temp % 10
        reverse_num = reverse_num * 10 + d
        temp //= 10
    return is_prime(reverse_num)

n = 97
print(solve(n))  # True

Đầu vào / Đầu ra

Input: 97
Output: True

Cải tiến: Hàm is_prime dùng vòng lặp đến sqrt(n) thay vì n để tăng tốc độ đáng kể cho số lớn.