Python - หาจำนวนตัวประกอบสูงสุดจากการคูณสองจำนวนในอาร์เรย์

ได้รับอาร์เรย์จำนวนเต็ม ต้องการหาจำนวนตัวประกอบ (factors) สูงสุดที่ได้จากการคูณสองจำนวนในอาร์เรย์ (cross product) ก่อนจะนับ factors ของผลคูณแต่ละคู่ แล้วหาค่าสูงสุด

ตัวอย่าง

Input: arr = [3, 2, 10]

Output: Maximum factors formed by two numbers are: 8

คำอธิบาย

1. Cross products: 3×2=6, 3×10=30, 2×10=20
2. Factors: 6→{1,2,3,6}(4), 30→{1,2,3,5,6,10,15,30}(8), 20→{1,2,4,5,10,20}(6)
3. สูงสุด = 8 (จาก 30)

Python Implementation

from math import isqrt
from itertools import combinations

def count_factors(n):
    """นับจำนวนตัวประกอบของ n (O(sqrt(n)))"""
    if n <= 0:
        return 0
    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_from_pair(arr):
    """หาจำนวน factors สูงสุดจากคู่อย่างใดอย่างหนึ่งในอาร์เรย์"""
    max_factors = 0
    best_pair = None
    best_product = 0
    
    for a, b in combinations(arr, 2):
        product = a * b
        factors = count_factors(product)
        if factors > max_factors:
            max_factors = factors
            best_pair = (a, b)
            best_product = product
    
    return max_factors, best_pair, best_product

# ทดสอบ
arr1 = [3, 2, 10]
result = max_factors_from_pair(arr1)
print(f"Array: {arr1}")
print(f"Max factors: {result[0]} (from {result[1]} = {result[2]})")

arr2 = [1, 4, 6]
result = max_factors_from_pair(arr2)
print(f"Array: {arr2}")
print(f"Max factors: {result[0]} (from {result[1]} = {result[2]})")

ผลลัพธ์

Array: [3, 2, 10]
Max factors: 8 (from (3, 10) = 30)

Array: [1, 4, 6]
Max factors: 8 (from (4, 6) = 24)

การเพิ่มประสิทธิภาพ (Optimization)

# Pre-compute factor counts สำหรับค่าที่อาจซ้ำ
from functools import lru_cache

@lru_cache(maxsize=None)
def count_factors_cached(n):
    if n <= 0:
        return 0
    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):
    max_f = 0
    best = None
    for a, b in combinations(arr, 2):
        f = count_factors_cached(a * b)
        if f > max_f:
            max_f = f
            best = (a, b)
    return max_f, best

Complexity Analysis

กรณีพิเศษ

• อาร์เรย์มี < 2 elements → ไม่มีคู่ คืน 0
• มี 0 → ผลคูณเป็น 0 มี factors มาก (ทุกจำนวนหาร 0 ลงตัว) ต้องจัดการแยก
• มีตัวเลขลบ → ใช้ค่าสัมบูรณ์สำหรับนับ factors