หาตัวประกอบเฉพาะทั้งหมด (Prime Factors) แบบมีประสิทธิภาพใน Python

โจทย์: หาตัวประกอบเฉพาะทั้งหมดของตัวเลข n (รวมซ้ำ)

อัลกอริทึมที่มีประสิทธิภาพ

1. หารด้วย 2 จนหมด (จัดการเลขคู่)
2. ลูปเลขคี่จาก 3 ถึง √n ก้าวละ 2
3. ถ้า n ที่เหลือ > 2 → เป็นเฉพาะตัวสุดท้าย

ตัวอย่างโค้ด Python

import math

def prime_factors(n):
    factors = []
    
    # หาร 2 จนหมด
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    # หารเลขคี่จาก 3 ถึง sqrt(n)
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    
    # เหลือ prime ตัวสุดท้าย
    if n > 2:
        factors.append(n)
    
    return factors

# ทดสอบ
print(prime_factors(200))  # Output: [2, 2, 2, 5, 5]

ผลลัพธ์

[2, 2, 2, 5, 5]

การใช้งาน

# พิมพ์ต่อเนื่อง (เหมือนต้นฉบับ)
n = 200
for factor in prime_factors(n):
    print(factor, end=' ')
# Output: 2 2 2 5 5

ความซับซ้อน: Time O(√n), Space O(log n) สำหรับเก็บผลลัพธ์