ใน Python ฉันจะเขียนโค้ดหาตัวประกอบของ54 ได้อย่างไร

นี่คือวิธีที่ผมชอบใช้เมื่ออยากแยกตัวประกอบของจำนวนหนึ่งอย่างเป็นระบบ: เริ่มจากหาปัจจัยเฉพาะ (prime factorization) แล้วนำผลลัพธ์ไปสร้างตัวประกอบทั้งหมดอีกที วิธีนี้ชัดเจนเวลาอยากรู้ทั้งรูปแบบเชิงพหุคูณและตัวประกอบย่อยๆ ของเลข เช่น 54 ซึ่งเป็นกรณีคลาสสิกเพราะมีทั้งเลขคู่และกำลังของ 3 ที่เยอะ

ผมมักเขียนฟังก์ชันแบบนี้ใน 'Python' เพื่อให้ได้พจนานุกรมของตัวประกอบพร้อมจำนวนกำลัง (exponent) ก่อน แล้วค่อยสร้างลิสต์ตัวประกอบทั้งหมดจากพวกนั้น:

def primefactors(n):
i = 2
factors = {}
while i i <= n:
while n % i == 0:
factors[i] = factors.get(i, 0) + 1
n //= i
i += 1 if i == 2 else 2
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors

def alldivisorsfrompf(pf):
divisors = [1]
for p, exp in pf.items:
divisors = [d (p e) for d in divisors for e in range(exp + 1)]
return sorted(divisors)

n = 54
pf = primefactors(n) # => {2:1, 3:3}
divs = alldivisorsfrompf(pf) # => [1,2,3,6,9,18,27,54]

วิธีนี้ให้ข้อมูลครบ ทั้งบอกว่า 54 = 2 3^3 และได้ตัวประกอบทั้งหมดพร้อมเรียง หากต้องการนำไปใช้งานต่อ เช่นหาจำนวนตัวหาร หรือตรวจสมบัติทางคณิตศาสตร์ วิธีนี้มีประสิทธิภาพพอสมควรสำหรับเลขขนาดกลาง และยังแก้ไขได้ง่ายเมื่ออยากขยายไปทำงานกับชุดตัวเลขหลายค่า ผมมักใช้วิธีนี้เวลาเขียนโค้ดช่วยวิเคราะห์โจทย์ที่ต้องการองค์ประกอบเชิงตัวประกอบแบบชัดเจน

ลองวิธีง่ายๆ แบบตรงไปตรงมาถ้าต้องการผลลัพธ์เร็วสำหรับเลขไม่ใหญ่มาก: ตรวจทุกจำนวนตั้งแต่ 1 จนถึงรากที่สองของ n แล้วเก็บคู่ตัวหาร i และ n//i วิธีนี้อ่านง่าย เห็นผลทันที และไม่ต้องคำนวณพหุคูณหรือพจนานุกรมซับซ้อน

ตัวอย่างโค้ดสั้นๆ ที่ผมมักใช้เวลาสอนเพื่อนใหม่:

import math

def divisors(n):
small = []
large = []
limit = int(math.sqrt(n))
for i in range(1, limit + 1):
if n % i == 0:
small.append(i)
if i != n // i:
large.append(n // i)
return small + large[::-1]

เมื่อรันกับ n = 54 ฟังก์ชันจะคืน [1, 2, 3, 6, 9, 18, 27, 54] ซึ่งตรงตามที่คาดไว้ วิธีนี้เหมาะกับงานที่อยากได้ตัวหารทั้งหมดแบบเรียงไว้ใช้ต่อ ในแง่ประสิทธิภาพ ถ้า n เล็กพอหรือปริมาณเรียกใช้ไม่มาก มันเรียบง่ายและอ่านได้ชัดเจนกว่าการทำ prime factorization โดยตรง นอกจากนี้ยังเป็นฐานความคิดที่ดีเมื่อต้องอธิบายแนวคิดการหา divisor ให้คนที่เพิ่งเริ่มเขียนโค้ดเข้าใจ โดยที่ไม่ต้องใช้เทคนิคซับซ้อนใดๆ

เคล็ดลับสั้นๆ ที่ผมใช้เวลาต้องการคำตอบแบบรวดเร็วและไม่อยากเขียนลูปเองคือใช้ไลบรารีที่มีอยู่แล้ว ตัวอย่างเช่น 'sympy' จะมีฟังก์ชันช่วยทั้งการแยกตัวประกอบและหาตัวหารทั้งหมด ถ้าติดตั้งได้ การเรียกใช้ง่ายมากและเหมาะเมื่อต้องทำงานวิจัยเล็กๆ หรือสคริปต์เพื่อทดสอบสมมติฐาน

ตัวอย่างการใช้:

from sympy import factorint, divisors

n = 54
pf = factorint(n) # pf => {2: 1, 3: 3}
alldivs = divisors(n) # alldivs => [1, 2, 3, 6, 9, 18, 27, 54]

ผมชอบวิธีนี้เมื่อต้องการผลลัพธ์ชัวร์และอยากประหยัดเวลาเขียนโลจิกพื้นฐานเอง แต่ก็ต้องยอมรับว่าเพิ่ม dependency และไม่เหมาะกับทุกโปรเจกต์ ถ้าเป็นงานเล็กๆ ที่แจกสคริปต์ให้คนอื่นใช้งาน อาจจะเลือกวิธีเขียนด้วยตัวเองแทน แต่สำหรับทดลองคณิตศาสตร์เล็กๆ การพึ่ง 'sympy' ช่วยให้โฟกัสกับปัญหาสำคัญได้มากขึ้นและลดโค้ดที่ต้องตรวจทาน