นับจำนวนที่หาร N ลงตัวแบบเร็วๆ

สมมติว่าเราต้องการหาว่าจำนวนทั้งหมดที่หาร 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 นะครับ

Taxonomy upgrade extras: