Truncatable Primes และผลรวมน้อยกว่า N
Truncatable Prime คือจำนวนเฉพาะที่ยังคงเป็นเฉพาะเมื่อตัดหลักซ้ายทีละหลัก (Left-truncatable) และตัดหลักขวาทีละหลัก (Right-truncatable) ตัวอย่าง: 9137 → 9137, 137, 37, 7 (ซ้าย) และ 9137, 913, 91, 9 (ขวา) แต่ 9 ไม่ใช่เฉพาะ → 9137 ไม่ใช่ Truncatable Prime จริง (ตัวอย่างในโจทย์อาจผิด) จริงๆ มีแค่ 15 ตัว: 2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,73939133
วิธีแก้
- Sieve of Eratosthenes หาเฉพาะทั้งหมด ≤ N
- สำหรับแต่ละเฉพาะ
p:- ตรวจสอบ Left-truncatable: ตัดหลักซ้ายซ้ำจนเหลือ 1 หลัก ทุกขั้นตอนต้องเป็นเฉพาะ
- ตรวจสอบ Right-truncatable: ตัดหลักขวาซ้ำ (mod 10, 100, ...) ทุกขั้นตอนต้องเป็นเฉพาะ
- รวมค่าที่ผ่านทั้งสองเงื่อนไข
โค้ดตัวอย่าง Python
def sieve(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5)+1):
if is_prime[i]:
for j in range(i*i, limit+1, i):
is_prime[j] = False
return is_prime
def is_truncatable(p, is_prime):
# left truncate
s = str(p)
for i in range(1, len(s)):
if not is_prime[int(s[i:])]:
return False
# right truncate
for i in range(1, len(s)):
if not is_prime[int(s[:i])]:
return False
return True
def sum_truncatable_primes(n):
is_prime = sieve(n)
total = 0
for i in range(2, n):
if is_prime[i] and is_truncatable(i, is_prime):
total += i
return total
print(sum_truncatable_primes(55)) # 2+3+5+7+23+37+53 = 130
