โปรแกรมหาตัวประกอบเฉพาะทั้งหมดของตัวเลขที่กำหนดเรียงลำดับใน Python

สมมติว่ามีตัวเลข n มากกว่า 1 เราต้องหาตัวประกอบเฉพาะทั้งหมดของมันและคืนค่าเรียงลำดับ ตัวเลขสามารถเขียนเป็นผลคูณของจำนวนเฉพาะได้ ตัวประกอบเฉพาะอาจปรากฏมากกว่าหนึ่งครั้ง

เช่น ถ้าอินพุตคือ 42 ผลลัพธ์จะเป็น [2, 3, 7]

ขั้นตอนการแก้ปัญหา

• res := รายการใหม่
• while n mod 2 เท่ากับ 0 ทำ
  • เพิ่ม 2 เข้าไปใน res
  • n := ผลหารของ n/2
• for i ในช่วง 3 ถึง (รากที่สองของ n) เพิ่มทีละ 2
  • while n mod i เท่ากับ 0 ทำ
    • เพิ่ม i เข้าไปใน res
    • n := ผลหารของ n/i
• ถ้า n > 2 แล้ว เพิ่ม n เข้าไปใน res
• คืนค่า res

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

class Solution:
    def solve(self, n):
        res = []
        while n % 2 == 0:
            res.append(2)
            n //= 2
        for i in range(3, int(n**0.5)+1, 2):
            while n % i == 0:
                res.append(i)
                n //= i
        if n > 2:
            res.append(n)
        return res

ob = Solution()
print(ob.solve(42))

อินพุต

42

เอาต์พุต

[2, 3, 7]