โปรแกรม Python หาเฉพาะตัวประกอบมากที่สุด (Largest Prime Factor) ของเลข

โจทย์: กำหนดจำนวนเต็มบวก n หาเฉพาะตัวประกอบมากที่สุด

แนวทาง

• Factorize โดยการหารด้วยตัวหารของเลข
• อัปเดต max prime factor ทุกครั้งที่หารลงตัว

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

import math

def maxPrimeFactor(n):
    while n % 2 == 0:
        max_Prime = 2
        n //= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            max_Prime = i
            n //= i
    if n > 2:
        max_Prime = n
    return int(max_Prime)

print(maxPrimeFactor(15))

ผลลัพธ์

5

Time Complexity: O(√n), Auxiliary Space: O(1)

สรุป

เรียนรู้วิธีหาเฉพาะตัวประกอบมากที่สุดของเลข: หาร 2 จนหมด แล้วหารเลขคี่ถึง sqrt(n) อัปเดตค่ามากที่สุด