สมมติว่าเราต้องการหาว่าจำนวนทั้งหมดที่หาร N ลงตัวมีกี่จำนวน เช่น จำนวนที่หาร 10 ลงตัวมี 4 จำนวน ได้แก่ 1, 2, 5 และ 10 และจำนวนที่หาร 25 ลงตัวมีทั้งหมด 3 จำนวน ได้แก่ 1, 5, 25 วิธีที่ง่ายที่สุดก็คือการวนรอบตั้งแต่ค่า 1 จนถึง N แล้วดูว่ามีจำนวนใดบ้างที่หาร N ลงตัวก็จะนับเพิ่ม 1 ครั้ง ซึ่งก็จะได้โค้ดออกมาหน้าตาประมาณนี้ครับ
typedef unsigned long long uint64; uint64 numberOfDivisor(uint64 n) { uint64 count = 0; for(int i = 1; i <= n; i++) if(n % i == 0) count++; return count; }
ในตัวอย่างโค้ดของบนจะพบว่าไม่ได้มีอะไรแปลกประหลาดมากครับ ใช้ uint64 แทน unsigned long long เพื่อให้สามารถรับค่ามากๆเป็นพารามิเตอร์ได้ เมื่อวิเคราะห์ความซับซ้อนของเวลาก็จะพบว่าอยู่ที่ O(n) เท่านั้น แต่ว่าถ้าเป็นกรณีที่ตัวเลขมีค่ามากๆเช่น 900,000,000 (เก้าร้อยล้าน) ถ้าลองรันโปรแกรมนี้ก็จะพบว่ามันนานได้ใจเหลือเกิน วันนี้จึงขอเสนอวิธีที่จะช่วยหาจำนวนที่หารลงตัวแบบเร็วขึ้นครับ
วิธีการต่อไปนี้จะใช้วิธีการหา prime factor ของ N ก่อน จากนั้นจะหาว่าเราสามารถสร้างจำนวนที่หาร N ลงตัวได้ทั้งหมดกี่วิธี ตัวอย่างเช่น 720 เกิดจาก 2 x 2 x 2 x 2 x 3 x 3 x 3 x 5 ดังนั้นเลขที่สามารถหาร 720 ลงตัวก็คือเลขที่สร้างจาก prime factor ของ 720 คูณกัน เช่น 2 x 2 = 4, 2 x 2 x 3 = 12, 3 x 3 = 9, 2 x 5 = 10 หรือ 2 x 3 x 5 = 30 เป็นต้น ตัวเลขเหล่านี้ล้วนหาร 720 ลงตัว
วิธีทั้งหมดที่เป็นไปได้ จะหาได้จากการนำเลขยกกำลังของจำนวนเฉพาะแต่ละตัวมาบวก 1 แล้วคูณกัน เช่น 720 มาจาก 2 x 2 x 2 x 2 x 3 x 3 x 3 x 5 ซึ่งก็คือ 24 x 32 x 51 ดังนั้นจำนวนที่หาร 720 มีทั้งหมด (4 + 1) x (2 + 1) x (1 + 1) = 30 จำนวนนั่นเอง (ส่วนวิธีหาลองคิดดูครับ ผมก็ไม่แม่นพอที่จะอธิบายให้เข้าใจได้ง่ายเช่นกัน)
ดังนั้นลองมาเขียนโปรแกรมกันใหม่ครับ ซึ่งคราวนี้อย่างน้อยๆเราจะต้องสร้างฟังก์ชันสำหรับสร้างจำนวนเฉพาะขึ้นมาเพื่อหาว่า N นั้นประกอบจากจำนวนเฉพาะใดบ้าง ซึ่งการสร้างจำนวนเฉพาะขึ้นมานั้นใช้เวลาไม่นาน เนื่องจากเราทราบว่าจำนวนเฉพาะที่หาร N ลงตัวนั้น(ไม่นับตัวมันเอง) จะต้องมีค่าน้อยกว่าหรือเท่ากันรากที่สองของ N แน่นอน (ไม่เชื่อลองหา N มาตัวนึง แล้วลองดูครับว่ามีค่าที่มากกว่ารากที่สองที่เป็นบวกของ N หาร N ลงตัวหรือไม่) พูดง่ายๆคือถ้า N เป็น 900,000,000 เราก็หาแค่จำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ sqrt(900,000,000) หรือ 30,000 เท่านั้นเอง
ซึ่งจะขอเสนอวิธีการสร้างจำนวนเฉพาะแบบเร็วๆ ตามโค้ดด้านล่าง เริ่มต้นด้วยการสร้าง vector สำหรับเก็บจำนวนเฉพาะที่สร้างขึ้น
vector<uint64> prime;
จากนั้นสร้างฟังก์ชันสำหรับตรวจสอบว่าจำนวนที่ส่งเข้ามาเป็นจำนวนเฉพาะหรือไม่ ด้วยการไปลองหารทุกตัวที่อยู่ใน vector prime (สังเกตุว่าเราไม่ได้หารทุกตัวที่น้อยกว่ามัน ซึ่งจะไม่กินเวลามาก)
bool isPrime(uint64 n) { if(n % 5 == 0) return false; for(uint64 i = 0; i < prime.size(); i++) if(n % prime[i] == 0) return false; return true; }
จากนั้นสร้างฟังก์ชันสำหรับสร้างจำนวนเฉพาะขึ้น แล้วเก็บลงใน vector prime
void genPrime(uint64 n){ prime.push_back(2); prime.push_back(3); prime.push_back(5); prime.push_back(7); for(uint64 i = 11; i*i <= n; i += 2) { if(i % 5 == 0) continue if(isPrime(i)) prime.push_back(i); } }
เริ่มต้นด้วยกันยัดเยียด 2, 3, 5 ,7 ลงไปแบบดื้อๆ บอกว่าเป็นจำนวนเฉพาะเลย จากนั้นเริ่มวนรอบตั้งแต่ค่า 11 ไปจนถึง sqrt(N) (ในที่นี้ผมยกกำลังสองทั้งสองข้างแทนนะครับ เลยเป็น i * i <= n ) จากนั้นก็ข้ามไปทีละ 2 พูดง่ายๆคือข้ามเลขคู่ไป เพราะมันหาร 2 ได้แน่นอน ในลูปก็จะข้ามตัวที่หาร 5 ลงตัวเช่นกัน แล้วก็เช็คว่า i เป็นจำนวนเฉพาะหรือไม่ ถ้าใช่ก็ใส่ลงไปใน vector prime ซะ
มาถึงฟังก์ชันสุดท้ายที่ใช้สำหรับหาจำนวนที่ N ลงตัว
uint64 numberOfDivisor2(uint64 n) { map<uint64> primeFactor; map<uint64>::iterator pit; uint64 count = 1, i; while(n > 1) { for(i = 0; i < prime.size(); i++) { if(n % prime[i] == 0) { n /= prime[i]; primeFactor[ prime[i] ] += 1; } } } for(pit = primeFactor.begin(); pit != primeFactor.end(); ++pit) count *= (*pit).second + 1; return count; }
ฟังก์ชัน numberOfDivisor2 ทำงานด้วยการหา prime factor ของ N แล้วนำเลขชี้กำลังของแต่ละตัวมาบวกด้วย 1 แล้วคูณกันตามวิธีด้านบน ซึ่งถ้าดูตามโค้ดก็จะใช้ map primeFactor เก็บจำนวนจำนวนเฉพาะแต่ละตัวว่ามีทั้งหมดกี่ตัว จากนั้นการวนรอบสุดท้ายก็จะทำการบวกด้วย 1 แล้วคูณสะสม ซึ่งคำตอบก็จะอยู่ที่ตัวแปร count นั่นเอง
หลังจากลองเรียกใช้ฟังก์ชัน numberOfDivisor2 แทน numberOfDivisor ในการหาจำนวนของตัวเลขที่หาร N ลงตัว จะพบว่าใช้เวลาเพียงไม่เท่าไหร่ก็สามารถหาได้แล้วว่ามีกี่ตัวที่หาร 900,000,000 ลงตัว (อย่าลืมเรียก genPrime ก่อน numberOfDivisor2 ด้วยนะครับ) นี่ก็เป็นตัวอย่างหนึ่งของการใช้ความรู้ทางคณิตศาสตร์เข้ามาช่วยแก้ปัญหา ซึ่งจะทำให้เราแก้ปัญหาได้อย่างมีประสิทธิภาพมากขึ้น
สามารถดาวน์โหลดโค้ดได้ที่นี่เลยนะครับ ==จิ้มเพื่อดาวน์โหลด== ถ้ามีข้อผิดพลาดประการใด ช่วยโพสบอกเอาไว้ด้วยนะครับ
ปล. วิธีที่เสนอมานี้เสนอมาด้วยความเบลอ มีอีกวิธีที่เร็วกว่าอยู่ในตอนที่ 2 นะครับ