โจทย์
จำนวนเต็มทุกจำนวนที่มากกว่า 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
ตัวอย่าง
อินพุต:
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]
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน