พอดีเมื่อวานผมเปิดอ่านหนังสือ Combinatorics ก็เห็นตัวอย่างโจทย์นับจำนวนที่หารลงตัวก็เลยบ้าจี้ลองเขียนโปรแกรมตามดู ซึ่งจริงๆแล้วเรามีวิธีที่สามารถคำนวนจำนวนที่หาร $N$ ลงตัวได้เร็วกว่า แล้วก็ง่ายกว่าด้วยครับ ไม่ต้องมานั่งหา prime ฮินดูอะไรนั่น เรียกได้ว่าสูงสุดคืนสู่สามัญจริงๆ ลองมาดูกันเลยครับ

วิธีนี้ก็จะประยุกต์จากเทคนิคที่ใช้หาค่า prime ในคราวก่อน นั่นคือวนรอบเท่ากับจำนวน $sqrt(N)$ ลองดูตัวอย่าง จำนวนที่หาร $N$ ลงตัวในแต่ละตัวดูครับ

30 = 1  2  3  5  6  10  15  30    (8 ตัว)

10 = 1  2  5  10    (4 ตัว)

64 = 1  2  4  8  16  32  64    (7 ตัว)

36 = 1  2  3  4  6  9  12  18  36    (9 ตัว)

สังเกตว่าการหารลงตัวครั้งนึงเราจะได้เลขสองตัวที่หาร $N$ ลงตัวมาเกือบทุกครั้ง เช่น 30 จะหาร 1 ลงตัวและ 30 ลงตัวด้วย ดังนั้นถ้าเราหารจำนวนใดลงตัวก็สามารถบวกเพิ่มไปทีละ 2 ได้เลย แต่เราจะต้องไม่นับครึ่งหลังของตัวหาร ซึ่งเราสามารถหาตัวกลางได้เสมอนั่นคือ $sqrt(N)$ นั่นเอง ดังนั้นวิธีนี้สามารถหาจำนวนที่หาร $N$ ลงตัวได้ในความซับซ้อนของเวลาเป็น O(n^0.5) หรือ O(sqrt(n)) เท่านั้น ตัวอย่างโค้ดคือ

uint64 numberOfDivisor3(uint64 n) {
    uint64 i, count = 0;
    for(i = 1; i * i <= n; i++)
        if(n % i == 0)
            count += 2;

    if((i-1)*(i-1) == n)
        count--;
    
    return count;    
}

โค้ดก็จะเหมือนกับคราวที่แล้ว คือวนรอบแล้วนับแต่คราวนี้เราจะนับขึ้นทีละสอง และหยุดเมื่อวนถึงค่าของ $sqrt(N)$ นอกจากนี้เรายังพบว่า บางครั้งจำนวนที่หาร $N$ ลงตัวก็มีค่าเป็นจำนวนคี่เช่นกัน ซึ่งจะเกิดขึ้นในกรณีที่ $sqrt(N)$ มีค่าเป็นจำนวนเต็มบวก เพราะจะทำให้เป็นการคูณตัวเอง ดังนั้นถ้าเจอกรณีนี้เราก็จะลบด้วย 1 ก่อน แล้วจึงส่งคำตอบกลับมา

จะเห็นว่าวิธีนี้เร็วกว่า แถมยังเขียนง่ายกว่ามาก แถมยังใช้หน่อยความจำน้อยกว่าอีกต่างหาก นอกจากนี้หากต้องการคำตอบว่าจำนวนที่หาร $N$ ลงตัวนั้นมีอะไรบ้างก็สามารถสร้าง structure ขึ้นมาตัวนึงเพื่อเก็บข้อมูลขณะทำงานได้เลย โดยที่โปรแกรมนี้ยังคงให้ความเร็วเท่าเดิมอยู่