ค้นหาคู่ที่มีค่า LCM น้อยที่สุดในอาร์เรย์ที่กำหนด

(สมมุติว่าเป็นจำนวนบวก)

LCM ที่เล็กที่สุดน่าจะมาจากองค์ประกอบที่เล็กที่สุด ดังนั้นเมื่อตัดค่าที่ลองแล้วก็สามารถเรียงลำดับอาร์เรย์ได้

int[] v = { ... };

int minLCM = Integer.MAX_VALUE;
int bestVi = -1;
int bestVj = -1;
Arrays.sort(v);
for (int i = 0; i < v.length; ++i) {
    int vi = v[i];
    //                                  _____________
    for (int j = i + 1; j < v.length && v[j] < minLCM; ++j) {
        int vj = v[j];
        int lcm = lcm(vi, vj);
        if (lcm < minLcm) {
            minLCM = lcm;
            bestVi = vi;
            bestVj = vj;
        }
    }
}

สำหรับการตัดแต่งกิ่ง:

lcm(vi, vj) >= vi
lcm(vi, vj) >= vj
(lcm(vi, vj) <= vi*vj

การตัดแต่งกิ่งนี้สามารถทำได้ใน for-j loop ในรูปแบบ vj >= vi เท่านั้น

การตัดแต่งกิ่งที่ดีขึ้นสามารถทำได้หากคุณมีรายการตัวประกอบเฉพาะ (สูงสุด ²log value) แทน เนื่องจากต้นทุนการแยกตัวประกอบก็อาจลองใช้ (2, 3, 5, 7) เป็นต้น

การวนซ้ำที่ดีขึ้นสามารถทำได้โดยการแทนที่ทั้งสองลูปที่ซ้อนกัน เพื่อให้ลูปที่เล็กที่สุด (vi, vj) มาก่อน ด้านบน (v0, v100) มาก่อน (v1, v2) วนซ้ำ i+j ที่เพิ่มขึ้น

i j
0 1
0 2
0 3
1 2
0 4
1 3
0 5
1 4
2 3
...

(คณิตศาสตร์สำหรับตัวนับลูปโดยใช้เส้นทแยงมุมเป็นปริศนาที่ดี ควรทำจริงๆ)

แม้ว่าจะยังคง O(n²) สิ่งนี้อาจใช้ได้ผล

บางครั้งภาษาการเขียนโปรแกรมก็มีความสำคัญ และเราเห็นว่าในบริบทเหล่านั้นมักจะมีส่วนสนับสนุนของ C ในกรณีเช่นนี้ การใช้ Ruby อาจมีผลเสีย