โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การแยกตัวประกอบเฉพาะ

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

สิ่งที่คุณจะได้เรียนรู้

  • หารตัวประกอบแต่ละตัวออกให้ครบตามจำนวนครั้งที่ปรากฏ
  • หยุดการหารทดลองเมื่อ d × d เกินส่วนที่เหลือ
  • เข้าใจว่าค่าที่เหลือและมากกว่า 1 คือตัวประกอบเฉพาะ

โจทย์

จำนวนเต็มทุกจำนวนที่มากกว่า 1 เขียนเป็นผลคูณของจำนวนเฉพาะได้เพียงแบบเดียว หากไม่นับลำดับของตัวประกอบ (ทฤษฎีบทหลักมูลของเลขคณิต) เช่น 360 = 2 × 2 × 2 × 3 × 3 × 5 การหารายการตัวประกอบนี้เรียกว่า การแยกตัวประกอบเฉพาะ

จงเขียน prime_factorization(n)

n อาจมีค่าได้ถึง 10^12 วิธีคลาสสิกคือการหารทดลอง (trial division) หาร 2 ออกไปจนกว่าจะหารไม่ลง แล้วต่อด้วย 3 และตัวถัด ๆ ไป ลองตัวหาร d เฉพาะตอนที่ d × d ≤ ส่วนของ n ที่ยังเหลืออยู่ก็พอ ถ้าตอนจบยังเหลือค่าที่มากกว่า 1 ค่านั้นเป็นจำนวนเฉพาะเอง วิธีนี้ใช้งานประมาณ √n ≈ 10^6 ขั้นเท่านั้น แม้ n จะเป็นจำนวนเฉพาะขนาดใหญ่หรือเป็นผลคูณของจำนวนเฉพาะขนาดใหญ่สองจำนวนก็ตาม

อินพุต

n: จำนวนที่ต้องการแยกตัวประกอบ

เอาต์พุต

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

เงื่อนไข

1 ≤ n ≤ 10^12

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 360

ผลลัพธ์ที่คาดหวัง:
expected = [2, 2, 2, 3, 3, 5]
อินพุต:
long long n = 360;

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
อินพุต:
long n = 360;

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

คำอธิบาย

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5 คำตอบจึงเป็น [2, 2, 2, 3, 3, 5]

ตัวอย่างที่ 2
อินพุต:
n = 97

ผลลัพธ์ที่คาดหวัง:
expected = [97]
อินพุต:
long long n = 97;

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {97};
อินพุต:
long n = 97;

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {97};

คำอธิบาย

ไม่มีจำนวนเฉพาะใดที่ไม่เกิน √97 ≈ 9.8 (คือ 2, 3, 5, 7) หาร 97 ลงตัว 97 จึงเป็นจำนวนเฉพาะ และคำตอบคือ [97]

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

หารด้วย 2 ไปเรื่อย ๆ จนกว่าจะหารไม่ลง แล้วเปลี่ยนเป็น 3, 5, 7 ตามลำดับ

คำใบ้ 2

ทุกครั้งที่เจอตัวประกอบให้ลดค่า n ลง และเทียบ d × d กับ n ที่ลดลงแล้ว

คำใบ้ 3

ถ้าหลังจบลูปยังเหลือค่าที่มากกว่า 1 ค่านั้นคือตัวประกอบเฉพาะที่ใหญ่ที่สุด

ความซับซ้อนที่คาดหวัง

เวลา O(√n), หน่วยความจำเพิ่ม O(log n) สำหรับผลลัพธ์

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก