Tìm tổng các số nguyên tố cắt cụt (truncatable primes) nhỏ hơn N trong Python

Cho số nguyên N, ta cần tìm tổng của tất cả các số nguyên tố cắt cụt (truncatable primes) nhỏ hơn N. Số nguyên tố cắt cụt là số vừa là left-truncatable prime (bỏ lần lượt chữ số đầu bên trái, các số còn lại đều nguyên tố) vừa là right-truncatable prime (bỏ lần lượt chữ số cuối bên phải, các số còn lại đều nguyên tố). Ví dụ: 9137 là số nguyên tố cắt cụt vì 9137, 137, 37, 7 đều nguyên tố.

Ví dụ, với N = 55, kết quả là 130 (2 + 3 + 5 + 7 + 23 + 37 + 53 = 130).

Thuật toán giải quyết

• Sàng Eratosthenes tạo mảng prime đến 1,000,005.
• Duyệt i từ 2 đến n-1:
  • Kiểm tra left-truncatable: liên tục chia 10, kiểm tra prime[current].
  • Kiểm tra right-truncatable: dùng power = 10, kiểm tra prime[current % power].
  • Nếu cả hai đều thỏa mãn, cộng i vào tổng.
• Trả về tổng.

Ví dụ minh họa

N = 1000005
prime = [True] * N

def sieve():
    prime[1] = prime[0] = False
    for i in range(2, N):
        if prime[i]:
            for j in range(i * 2, N, i):
                prime[j] = False

def get_total_of_trunc_primes(n):
    total = 0
    for i in range(2, n):
        current = i
        f = True
        while current:
            if not prime[current]:
                f = False
                break
            current //= 10
        current = i
        power = 10
        while current // power:
            if not prime[current % power]:
                f = False
                break
            power *= 10
        if f:
            total += i
    return total

n = 55
sieve()
print(get_total_of_trunc_primes(n))  # 130

Đầu vào

55

Đầu ra

130