การแยกตัวประกอบจำนวนเฉพาะและตัวหาร
แยก N เป็นกำลังของจำนวนเฉพาะและนับตัวหาร
การแยกตัวประกอบจำนวนเฉพาะและตัวหาร เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 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) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร”
แยก N เป็นกำลังของจำนวนเฉพาะและนับตัวหาร คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “การแยกตัวประกอบจำนวนเฉพาะและตัวหาร” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- GCD, LCM และอัลกอริทึมยูคลิด
- การทดสอบจำนวนเฉพาะถึง sqrt(n)
- ตะแกรงของเอราโตสเทนีส
- การแยกตัวประกอบจำนวนเฉพาะและตัวหาร