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

ব্যাখ্যা:

• সম্ভাব্য জোড়াগুলো এবং গুণফল:
  • 3 × 2 = 6 → ফ্যাক্টর: 1, 2, 3, 6 (৪টি)
  • 3 × 10 = 30 → ফ্যাক্টর: 1, 2, 3, 5, 6, 10, 15, 30 (৮টি)
  • 2 × 10 = 20 → ফ্যাক্টর: 1, 2, 4, 5, 10, 20 (৬টি)
• সর্বোচ্চ ফ্যাক্টর: ৩০-র ৮টি → আউটপুট ৮

পাইথন সমাধান

from math import isqrt
from itertools import combinations

def count_factors(n: int) -> int:
    """একটি সংখ্যার ফ্যাক্টর সংখ্যা গণনা (O(√n))"""
    count = 0
    for i in range(1, isqrt(n) + 1):
        if n % i == 0:
            count += 1 if i == n // i else 2
    return count

def max_factors_pair_product(arr: list) -> int:
    """অ্যারে থেকে দুটি সংখ্যা বেছে নিয়ে সর্বোচ্চ ফ্যাক্টর বের করা"""
    max_factors = 0
    
    # সব সম্ভাব্য জোড়া (combination of 2)
    for a, b in combinations(arr, 2):
        product = a * b
        factors = count_factors(product)
        max_factors = max(max_factors, factors)
    
    return max_factors

# টেস্ট
print(max_factors_pair_product([3, 2, 10]))   # 8
print(max_factors_pair_product([1, 4, 6]))    # 8 (1*4=4:3, 1*6=6:4, 4*6=24:8)
print(max_factors_pair_product([2, 3, 5, 7])) # 4 (সব প্রাইম, গুণফলে ৪ ফ্যাক্টর)

অপ্টিমাইজড ভার্সন (বড় ইনপুটের জন্য)

from math import isqrt
from itertools import combinations
from functools import lru_cache

@lru_cache(maxsize=None)
def count_factors_cached(n: int) -> int:
    """মেমোইজেশন সহ ফ্যাক্টর কাউন্ট"""
    count = 0
    for i in range(1, isqrt(n) + 1):
        if n % i == 0:
            count += 1 if i == n // i else 2
    return count

def max_factors_optimized(arr: list) -> int:
    max_factors = 0
    for a, b in combinations(arr, 2):
        max_factors = max(max_factors, count_factors_cached(a * b))
    return max_factors

আলগরিদমিক কমপ্লেক্সিটি

আরো দ্রুত পদ্ধতি: প্রাইম ফ্যাক্টরাইজেশন

ফ্যাক্টর সংখ্যা = (e₁+1)(e₂+1)...(eₖ+1) যেখানে eᵢ হলো প্রাইম ফ্যাক্টরের এক্সপোনেন্ট।

def prime_factors_count(n: int) -> int:
    """প্রাইম ফ্যাক্টরাইজেশন দিয়ে ফ্যাক্টর সংখ্যা (O(√n) কিন্তু কম কনস্ট্যান্ট)"""
    count = 1
    d = 2
    while d * d <= n:
        exp = 0
        while n % d == 0:
            n //= d
            exp += 1
        if exp:
            count *= (exp + 1)
        d += 1 if d == 2 else 2  # 2 পরে শুধু বিজোড় চেক
    if n > 1:
        count *= 2
    return count

এজ কেস হ্যান্ডলিং

• অ্যারে সাইজ < 2 হলে: রিটার্ন ০ বা ইরর
• নেগেটিভ নাম্বার: অ্যাবসোলিউট ভ্যালু নিন
• শূন্য (0) থাকলে: 0 × যেকোনো = 0, যার অসংখ্য ফ্যাক্টর (স্পেশ্যাল হ্যান্ডলিং) — সাধারণত 0 এক্সক্লুড করা হয়
• ডুপ্লিকেট নাম্বার: combinations ইন্ডেক্স বেসড, তাই ডুপ্লিকেট আলাদা জোড়া হিসেবে গिना যাবে