Kiểm tra số nguyên tố Dihedral trong Python

Một số được gọi là số nguyên tố Dihedral (dihedral prime) khi nó là số nguyên tố và khi hiển thị trên màn hình 7 đoạn (7-segment display), số đó vẫn là số nguyên tố dù màn hình được xem ở trạng thái bình thường hay ngược (up-side down).

Ví dụ: n = 1181 trả về True vì cả 1181 và dạng ngược của nó đều là số nguyên tố.

Giải thuật

Định nghĩa hàm up_side_down(n) chuyển đổi số theo quy tắc: 2 ↔ 5, các chữ số khác giữ nguyên, sau đó đảo ngược thứ tự chữ số.
Sử dụng sàng Eratosthenes để kiểm tra số nguyên tố nhanh chóng.
Kiểm tra: n, up_side_down(n), đảo ngược của n, đảo ngược của up_side_down(n) đều phải là số nguyên tố.
Ngoài ra, các chữ số của n không được chứa 3, 4, 6, 7, 9 (vì chúng không thể hiển thị trên màn hình 7 đoạn khi ngược).

Mã ví dụ

prime = (int(1e5)+5)*[True]

def reverse(n):
    return int(str(n)[::-1])

def up_side_down(n):
    temp = n
    total = 0
    while temp > 0:
        d = temp % 10
        if d == 2:
            d = 5
        elif d == 5:
            d = 2
        total = total * 10 + d
        temp //= 10
    return total

def get_all_prime():
    prime[0] = prime[1] = False
    for i in range(2, int(1e5)+1):
        j = 2
        while i * j <= int(1e5):
            prime[i * j] = False
            j += 1

def solve(n):
    get_all_prime()
    if not prime[n] or not prime[up_side_down(n)] or not prime[reverse(n)] or not prime[reverse(up_side_down(n))]:
        return False
    temp = n
    while temp > 0:
        rem = temp % 10
        if rem in [3, 4, 6, 7, 9]:
            return False
        temp //= 10
    return True

n = 1181
print(solve(n))

Đầu vào

Đầu ra

True