পাইথনে N-এর নিচে সব ট্রানকেটেবল প্রাইমের যোগফল বের করুন

সমস্যা বিবরণ

একটি ইন্টিজার N দেওয়া আছে। N-এর চেয়ে ছোট সব ট্রানকেটেবল প্রাইমের যোগফল বের করতে হবে। ট্রানকেটেবল প্রাইম হলো এমন প্রাইম যেটি বাম পাশ থেকে অঙ্ক মুছে দিলেও (লেফট-ট্রানকেটেবল) এবং ডান পাশ থেকে অঙ্ক মুছে দিলেও (রাইট-ট্রানকেটেবল) প্রাইমই থাকে। উদাহরণ: 9137 (৯১৩৭, ১৩৭, ৩৭, ৭ সব প্রাইম)।

উদাহরণস্বরূপ, N=55 হলে আউটপুট 130 (২+৩+৫+৭+২৩+৩৭+৫৩ = ১৩০)।

সমাধানের ধাপসমূহ

1. N = 1000005 সাইজের সিভ (Sieve) দিয়ে প্রাইম টেবিল বানান।
2. প্রতিটি সংখ্যা i = 2 থেকে n-1 পর্যন্ত:
   • লেফট-ট্রানকেটেবল চেক: বারবার ১০ দিয়ে ভাগ করে প্রাইম কিনা দেখুন।
   • রাইট-ট্রানকেটেবল চেক: power = 10 থেকে শুরু করে i % power প্রাইম কিনা দেখুন, power *= 10।
   • দুটি শর্ত পূরণ করলে যোগফলে যোগ করুন।
3. যোগফল রিটার্ন করুন।

পাইথন কোড উদাহরণ

N = 1000005
prime = [True] * N

def sieve():
    prime[0] = prime[1] = 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
        # left-truncatable
        while current:
            if not prime[current]:
                f = False
                break
            current //= 10
        # right-truncatable
        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

ইনপুট

55

আউটপুট

130