0Pricing
Coding Interview Prep · บทเรียน

การแยกตัวประกอบจำนวนเฉพาะและตัวหาร

แยก N เป็นกำลังของจำนวนเฉพาะและนับตัวหาร

การแยกตัวประกอบจำนวนเฉพาะและตัวหาร เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

แยก N ออกเป็นตัวประกอบ

จำนวนเต็มทุกจำนวนที่มากกว่า 1 เป็นผลคูณของจำนวนเฉพาะที่มีรูปแบบเฉพาะตัว การค้นหาการแยกนั้น หรือการแยกตัวประกอบจำนวนเฉพาะ จะช่วยไขโจทย์ทฤษฎีจำนวนได้มากมาย 🧩

แนวคิดการหารทดลอง

ดึงจำนวนเฉพาะที่เล็กที่สุดซึ่งหาร n ลงตัวออกมา หารมันออก แล้วทำซ้ำ การหารทดลองแบบง่ายนี้จะแยก n ลงจนเหลือ 1

วนไปจนถึงรากที่สอง

ทดสอบตัวหาร i ตราบใดที่ i*i ยังน้อยกว่าหรือเท่ากับ n หลังผ่านรากที่สองแล้ว จะเหลือตัวประกอบจำนวนเฉพาะได้อย่างมากหนึ่งตัว

while i * i <= n:
    ...

ดึงตัวประกอบแต่ละตัวออกมา

ตราบใดที่ i หาร n ลงตัว ให้หารต่อไปและบันทึก i วิธีนี้จะเก็บกำลังทั้งหมดของจำนวนเฉพาะนั้นก่อนดำเนินการต่อ

while n % i == 0:
    factors.append(i)
    n //= i

จำนวนเฉพาะที่เหลือ

หลังจบลูป หาก n ยังมากกว่า 1 แสดงว่า n เองเป็นตัวประกอบเฉพาะที่มีค่ามากกว่ารากที่สอง ให้เพิ่มมันหนึ่งครั้ง

if n > 1:
    factors.append(n)

กระบวนการทั้งหมด

เมื่อนำทุกอย่างมารวมกัน จะได้การแยกตัวประกอบที่ใช้เวลา O(sqrt n) และคืนค่าจำนวนเฉพาะทุกตัวพร้อมจำนวนครั้งที่ปรากฏครบถ้วนตามลำดับ

def factorize(n):
    f, i = [], 2
    while i * i <= n:
        while n % i == 0:
            f.append(i); n //= i
        i += 1
    if n > 1: f.append(n)
    return f

จัดกลุ่มเป็นกำลัง

สำหรับการนับตัวหาร คุณต้องการจำนวนเฉพาะแต่ละตัวพร้อมเลขชี้กำลังของมัน เช่น 2^3 ไม่ใช่ 2,2,2 ตัวนับจะนับจำนวนที่ซ้ำกันให้เป็นระเบียบ

from collections import Counter
exp = Counter(factorize(n))

สูตรหาจำนวนตัวหาร

ถ้า n เท่ากับ p1^a คูณ p2^b จำนวนตัวหารจะเท่ากับ (a+1) คูณ (b+1) เพราะเลขชี้กำลังแต่ละตัวมีตัวเลือกเพิ่มอีกหนึ่งค่า

นับจำนวนตัวหาร

คูณหนึ่งบวกเลขชี้กำลังของจำนวนเฉพาะแต่ละตัวเข้าด้วยกัน วิธีนี้จะได้จำนวนตัวหารทั้งหมดโดยไม่ต้องไล่แสดงตัวหารทีละตัว

count = 1
for e in exp.values():
    count *= (e + 1)

หาผลรวมของตัวหาร

มีสูตรที่เกี่ยวข้องกันสำหรับหาผลรวมตัวหาร โดยใช้อนุกรมเรขาคณิตของจำนวนเฉพาะแต่ละตัว การรู้สูตรนี้มีประโยชน์กับปัญหาจำนวนสมบูรณ์และปัญหาเกี่ยวกับผลบวกตัวหารแท้

เพิ่มความเร็วด้วยตะแกรง

หากต้องแยกตัวประกอบหลายจำนวน ให้คำนวณตัวประกอบเฉพาะที่เล็กที่สุดของแต่ละจำนวนไว้ล่วงหน้าด้วยตะแกรง จากนั้นการแยกตัวประกอบของแต่ละคำขอจะใช้เวลา log n ขั้นตอน

ตรวจสอบอย่างรวดเร็ว

ใช้สูตรนับจำนวนตัวหารกับจำนวนจริงสักจำนวนหนึ่ง

ทบทวน

ตอนนี้คุณสามารถแยกตัวประกอบ N ด้วยการหารลองในเวลา O(sqrt n) เก็บจำนวนเฉพาะที่เหลือ จัดกลุ่มเลขชี้กำลัง และนับตัวหารด้วยสูตรผลคูณได้แล้ว ✅

คำถามที่พบบ่อย

บทเรียน “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร”

แยก N เป็นกำลังของจำนวนเฉพาะและนับตัวหาร คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. GCD, LCM และอัลกอริทึมยูคลิด
  2. การทดสอบจำนวนเฉพาะถึง sqrt(n)
  3. ตะแกรงของเอราโตสเทนีส
  4. การแยกตัวประกอบจำนวนเฉพาะและตัวหาร
← กลับไปที่ Coding Interview Prep