পাইথনে যাচাই করুন কোনো পূর্ণসংখ্যা দুই সেমি-প্রাইমের যোগফল হিসেবে প্রকাশ পায় কিনা

ধরুন, আমাদের একটি সংখ্যা n দেওয়া হয়েছে। আমাদের যাচাই করতে হবে যে n কি দুটি সেমি-প্রাইম সংখ্যার যোগফল হিসেবে প্রকাশ পেতে পারে।

সেমি-প্রাইম হলো এমন সংখ্যা যা দুটি প্রাইম সংখ্যার গুণফল হিসেবে লেখা যায়। ১ থেকে ১০০ পর্যন্ত সেমি-প্রাইম সংখ্যাগুলো হলো: ৪, ৬, ৯, ১০, ১৪, ১৫, ২১, ২২, ২৫, ২৬, ৩৩, ৩৪, ৩৫, ৩৮, ৩৯, ৪৬, ৪৯, ৫১, ৫৫, ৫৭, ৫৮, ৬২, ৬৫, ৬৯, ৭৪, ৭৭, ৮২, ৮৫, ৮৬, ৮৭, ৯১, ৯৩, ৯৪, ৯৫।

যেমন, ইনপুট n = 108 হলে আউটপুট হবে True, কারণ ১০৮ = ১৪ + ৯৪ (দুটোই সেমি-প্রাইম)।

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

MAX = 10000 ধরুন (মানুষের ইনপুট এই রেঞ্জে থাকবে বলে ধরে)।
nums নামক একটি খালি লিস্ট এবং s_prime_flags নামক MAX সাইজের বুলিয়ান অ্যারে (শুরুতে সব False) নিন।
get_semi_primes() ফাংশন সংজ্ঞায়িত করুন:
- i = 2 থেকে MAX-1 পর্যন্ত লুপ চালান।
- প্রতিটি i এর জন্য এর প্রাইম ফ্যাক্টর গণনা করুন। যদি মোট ২টি প্রাইম ফ্যাক্টর পাওয়া যায় (গুনিতক সহ), তবে s_prime_flags[i] = True করুন এবং i-কে nums-এ যোগ করুন।
মূল ফাংশনে get_semi_primes() কল করুন।
i = 0 থেকে শুরু করে যতক্ষণ nums[i] <= n // 2:
- যদি s_prime_flags[n - nums[i]] True হয়, তবে True ফেরত দিন।
- i বাড়ান।
লুপ শেষ হলে False ফেরত দিন।

উদাহরণ কোড

MAX = 10000
nums = []
s_prime_flags = [False] * MAX

def get_semi_primes():
    for i in range(2, MAX):
        count = 0
        num = i
        j = 2
        while count < 2 and j * j <= num:
            while num % j == 0:
                num //= j
                count += 1
            j += 1
        if num > 1:
            count += 1
        if count == 2:
            s_prime_flags[i] = True
            nums.append(i)

def solve(n):
    get_semi_primes()
    i = 0
    while nums[i] <= n // 2:
        if s_prime_flags[n - nums[i]]:
            return True
        i += 1
    return False

n = 108
print(solve(n))

ইনপুট

আউটপুট

True